AcWing 900. 整数划分
原题链接
简单
作者:
xxxx_XXXXX
,
2021-03-28 15:01:59
,
所有人可见
,
阅读 164
/*
转为背包问题;容量为n,一共有n个物品。每个物品体积为i (i = 1 ; i <= n ; i++ )
f[i][j]表示选前i个物品,体积恰好j的选取方案数量
f[i][j] = f[i-1)[j] + f[i-1][j-k*cap]
不选当前i, 选k个i
通过具体表示f[i][j] 以及f[i][j-i],可以发现
if(j>= caps)
f[i][j] = f[i-1)[j] + f[i-1][j-i] ;
dp[i][j] = max(f[i][j]) ;
*/
#include <bits/stdc++.h>
using namespace std ;
const int N = 1010;
const int mod = 1e9 + 7 ;
int dp[N][N] ;
int main(){
int all ; cin >> all ;
for(int i = 0 ; i <=all ;i++) dp[i][0] = 1 ;//容量为0时候 前i个物品一个也不选也是一种方案
for(int i = 1 ; i <= all ; i++){
int cap = i ;
for(int j = 0 ; j <= all ; j++)
{
if(j>=cap)
dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % mod ;
else
dp[i][j] = dp[i-1][j] % mod ; //不选当前i,且满足背包容量为j的选取个数
// if(j>=cap)
// for(int k = 1 ; k*cap <=j ; k++) //选k个i
// dp[i][j] = (dp[i][j] + dp[i-1][j-k*cap]) % mod; //一定要注意f[i][j] = f[i-1)[j] + f[i-1][j-k*cap]
//. k = 0 , k = 1 , k = 2 , k ...
}
}
cout<<dp[all][all] ;
return 0;
}