蓝桥杯算法提高VIP-数的划分

题目

题目链接

题解

动态规划。

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