[Acwing] 279. 自然数拆分 完全背包求解方案数

前言

传送门 :

思路

题意转换 从 1 到 ( n − 1 ) 1到(n-1) 1到(n−1)个数中,每个数可以选取无限次,询问 和 为 i 和为i 和为i有多少种方案

为什么是 n-1 因为题目要求 最少都要拆成 两个数的和

所以状态表示 f [ i ] [ j ] f[i][j] f[i][j]前 i i i个数中选,和为 j j j的所有方案数

同时根据完全背包的一维优化

我们可以优化为一维

只不过 第二层循环需要从 v − m v - m v−m

Mycode

const int N  = 4e3+10 ;
const ll mod = 2147483648;


ll f[N];

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