整数划分

分析-完全背包思想

DP分析

  • 状态表示 f[i][j]f[i][j]
    • 集合：类比完全背包问题，表示将jj划分为前ii个数组合的集合
    • 属性：集合元素个数
  • 状态计算-类比完全背包问题：
    f[i][j]=f[i−1][j]+f[i−1][j−i]+f[i−1][j−2i]+...+f[i−1][j−ni](ni<=j)f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2i]+...+f[i-1][j-ni] (ni <= j )
    f[i][j−i]=f[i−1][j−i]+f[i−1][j−2i]+f[i−1][j−3i]+...+f[i−1][j−ni](ni<=j)f[i][j -i] = f[i-1][j -i] + f[i-1][j-2i] + f[i-1][j-3i]+...+f[i-1][j-ni] (ni <= j )
    所以有：
    f[i][j]=f[i−1][j]+f[i][j−i]f[i][j] = f[i-1][j]+f[i][j-i]

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e3+10,mod = 1e9+7;
int f[N][N];

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n; i ++ ) f[i][0] = 1;
  
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ){
            f[i][j] = f[i-1][j]%mod;
            if(j >= i)
                f[i][j] = (f[i-1][j] + f[i][j-i]) % mod;
        }
   ;
    
    cout << f[n][n] % mod;
    
    return 0;
}

Q.E.D.