[Acwing] 算法基础课汇总五 动态规划 二

计数类DP

1.整数划分

题意 :
给定一个数 n n n,询问有多少种方法可以将其拆分成多个数的和,包括本身

思路 :
此题模板于 Acwing.自然数的拆分
状态表示与转移同理于01背包记录方案数

状态表示 :
f [ i ] f[i] f[i]表示 i i i拆分的所有组合

状态转移 :

$f[j] = f[j]+f[j-i]$

const int N  = 4e3+10 ;
const ll mod = 1e9+7;


ll f[N];

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