【数字组合】
题目
思路
状态表示：
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;
}