[Acwing] 900. 整数划分 计数DP

计数dp 有点想 背包问题啊

做过 记搜 的题 可以说 一模一样

状态表示:
f [i][j] 表示从前 i 个整数 选出 恰好和为 j 的方案

状态转移 :

如果当前小于 i 那么 可以由上一层 f[i - 1][j] 推导过来

否则 即 f [ i ] = f [ i − 1 ] [ j ] + f [ i ] [ j − i ] ) f[i]=f[i-1][j] + f[i][j-i]) f[i]=f[i−1][j]+f[i][j−i])

这不就是背包的推导吗

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


void solve()
{
    cin>>n;
    for(int i= 0 ;i<=n;i++)
    f[i][0] = 1;

    for(int i=1;i<=n;i++)
    {
        for(int j = 0 ;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<