题目
题目链接
题解动态规划。
dp[i][j]表示用1~i这些数构造出j这个数的方案数；
转移方程：
含义为：对于每一个数i我们都可以选k次，要想构成j，则由前i-1个数构成j-k*i。
边界为：dp[i][0] = 1，构成0的方案数为1，即都不选。
其实由上面的式子可以简化一层循环，转移方程为：dp[i][j] = dp[i-1][j] + (j>=i?dp[i][j-i]:0) 当j>=i时，dp[i][j] = dp[i-1][j] + dp[i][j-i]，否则，dp[i][j] = dp[i-1][j]。
因为dp[i][j-i]是已经在本次内循环中更新过了，所以它的含义已经是选了第i个数的方案数了（但又不完全是）。 这里其实和0-1背包里面的二维变成一维是原理是一样的，实在不理解可以把这个二维矩阵的更新过程模拟一遍。
原生态代码#include using namespace std; const int N = 110; int dp[N][N], n, ans; int main() { cin>>n; for(int i = 0;i <= n;i ++) dp[i][0] = 1; for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) for(int k = 0;k*i <= n && k*i <= j;k ++) // 第j个i个数用k次 dp[i][j] += dp[i-1][j-k*i]; cout << dp[n][n] << endl; return 0; }
经过变形代码
#include using namespace std; const int N = 110; int dp[N][N], n, ans; int main() { cin>>n; for(int i = 0;i <= n;i ++) dp[i][0] = 1; for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) dp[i][j] = dp[i-1][j] + (j>=i?dp[i][j-i]:0); cout << dp[n][n] << endl; return 0; }
