题目
思路
状态表示:
f [ i ] [ j ] f[i][j] f[i][j] 对应考虑1到 i 号数字,和为 j 的方法,表示方法数
目标表示:
f [ n ] [ m ] f[n][m] f[n][m]
状态转移:
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − a [ i ] ] f[i][j] = f[i-1][j] + f[i-1][j-a[i]] f[i][j]=f[i−1][j]+f[i−1][j−a[i]] 即选和不选
初始化:
f [ i ] [ 0 ] = 1 f[i][0] = 1 f[i][0]=1 表示一种方法,注意这里的 i ∈ [ 0 , n ] i \in [0,n] i∈[0,n]
优化:
见代码
代码
#include <bits/stdc++.h>
using namespace std;
int f[110][10010];
int main()
{int n, m;cin >> n >> m;f[0][0] = 1;for(int i = 1; i <= n; i++){f[i][0] = 1;int a;cin >> a;for(int j = 1; j <= m; j++){f[i][j] = f[i-1][j];if(j >= a) f[i][j] += f[i-1][j-a];}}cout << f[n][m];return 0;
}
#include <bits/stdc++.h>
using namespace std;
int f[10010];
int main()
{int n, m;cin >> n >> m;f[0] = 1;for(int i = 1; i <= n; i++){int a;cin >> a;for(int j = m; j >= a; j--){f[j] += f[j-a];}}cout << f[m];return 0;
}