[Acwing] 278. 数字组合 01背包

前言

传送门 :

思路

状态表示 f [ i ] [ j ] f[i][j] f[i][j] 从前 i i i个数中选 和为 j j j的数

状态计算 :

• 选当前的数, f [ i ] [ j ] + = f [ i − 1 ] [ j − a [ i ] ] f[i][j] += f[i-1][j-a[i]] f[i][j]+=f[i−1][j−a[i]]
• 不选当前的数, f [ i ] [ j ] + = f [ i − 1 ] [ j ] f[i][j] +=f[i-1][j] f[i][j]+=f[i−1][j]

显然根据 01 01 01背包的一维优化,我们同理也可也优化,因此这个就成 模板题了

Mycode

const int N  = 1e5+10;
int f[N];

void solve()
{
	int n,m;cin>>n>>m;
	
	f[0] = 1;
	for(int i=1;i>x;
		for(int j = m;j>=x;j -- ){
			f[j]  += f[j-x];
		}
	}
	cout