[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])

这不就是背包的推导吗

CODE

/**
前 i 个整数 恰好和为 j 的方案

状态转移
f[i][j] = 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