【算法基础】计数类DP AcWing 900. 整数划分 (闫氏dp分析法)

链接
给定一个正整数n，问有多少种方案使得n=x1+x2+…+xn，因此不需要考虑顺序。

5的所有情况↓

闫氏DP分析法：
状态表示： f [ i ] [ j ] f[i][j] f[i][j] 表示所有1~i中选，且体积恰好是j的选法的数量
属性:COUNT
状态计算:
推导过程↓

其中s表示选i的个数
数学归纳法
得出状态表示: f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] f[i][j] = f[i - 1][j] + f[i][j - 1] f[i][j]=f[i−1][j]+f[i][j−1]
根据完全背包的思路可以优化为一维:
f [ j ] = f [ j ] + f [ j − i ] f[j] = f[j] + f[j - i] f[j]=f[j]+f[j−i]

#include 
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n,f[N];
int main () {
  cin >> n;
  f[0] = 1;
  for(int i = 1;i <= n; i ++) {//从小到大开始枚举 
    for(int j = i; j <= n; j ++) {//需要从1 开始
      f[j] = (f[j] + f[j - i]) % mod;
    }
  }
  cout << f[n] << endl;
  return 0;
}

由于是按位数计算的，最后结果需要把每个区间都加上

#include 
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n,f[N][N];
int main () {
  cin >> n;
  f[0][0] = 1;//初始化
  for(int i = 1; i <= n; i ++) {//枚举总和
    for(int j = 1; j <= i; j ++) {// 枚举个数到 i (全部用1表示)
      f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;//划分为最小值是1 和 >1
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    ans = (ans + f[n][i]) % mod;
  }
  cout << ans << endl;
  return 0;
}