题目

---

思路

状态表示： $f[i][j]$ 对应考虑1到 i 号数字，和为 j 的方法，表示方法数
目标表示： $f[n][m]$
状态转移： $f[i][j]=f[i-1][j]+f[i-1][j-a[i]]$ 即选和不选
初始化： $f[i][0]=1$ 表示一种方法，注意这里的 $i\in [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;
}