动态规划：计数类DP

 整数划分：

二维做法：

#include <iostream>using namespace std;const int N = 1e3 + 7, mod = 1e9 + 7;int f[N][N];int main() 
{int n;scanf("%d",&n);//总数为0时，前i个数字全不选也是一种方案，但某个数字不选并不是一种方案//而这里只用把[0][0]初始化，而不是把所有[i][0]，因为在下面每次循环到j==0时都会让[i][0]=[i-1][0]=0f[0][0] = 1;for (int i = 1; i <= n; i ++) {for (int j = 0; j <= n; j ++) {   if(j<i)//当前总数小于i个数字，则说明无法再选数字了，方案数就是前几个数字的方案数f[i][j] = f[i - 1][j] % mod; //f[0][0] = 1else//当前总数大于等于i个数字，则说明可以选数字了。//不要i能到总数j的方案数+要i能到总数j-i的方案数==前i个数字能到总数j的方案数f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;}}printf("%d\n",f[n][n]);return 0;
}

一维做法：

#include <iostream>using namespace std;const int N = 1e3 + 7, mod = 1e9 + 7;int f[N];int main() 
{int n;scanf("%d",&n);f[0] = 1; //总数为0时，前i个数字全不选也是一种方案，但某个数字不选并不是一种方案for (int i = 1; i <= n; i ++)//前i个数字{for (int j = i; j <= n; j ++)//总数为j{   //不要i能到总数j的方案数+要i能到总数j-i的方案数==前i个数字能到总数j的方案数//这里不是二维，所以没法纪录i，但i是递增的且在外循环，所以每次用到的都在前面已经算出来了//例：当前i==4,j==5:f[5]在i==3,j==5时算出来了，也就是不要4能到总数5的方案数//                  f[1]在i==4,j==1时算出来了，也就是  要4能到总数1的方案数f[j]=(f[j] + f[j - i]) % mod;}}printf("%d\n",f[n]);return 0;
}