01背包求方案数,这题的方案数是一种组合,即数字之间不管顺序。以下思路参考的是二维dp数组的思路而不是滚动数组的思路,因为二维dp数组思路更为清晰,且更能体现出集合的思想。
dp[i][j]
的定义:考虑 nums[1:i] 这些数字,且满足这些数字的和恰好等于 j 的可选方案数。
状态转移公式:dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
dp[i - 1][j]
表示不考虑加上 nums[i]
就能满足和恰好等于 j 的方案数。
dp[i - 1][j - nums[i]]
表示考虑加上 nums[i]
的时候,还差加上 nums[i]
这最后一步其总和就等于 j 的方案数。
这一个考虑和一个不考虑就已经包含完了所有可能情况,相加就是 dp[i][j]
的结果。
初始化:第 i 个数的和等于 0 的方案数始终 = 1。从题目层面来讲,任何一个数的和想要=0那只有不加这个数这一种方案;从程序层面来讲,如果不设为1,初始化 dp 数组全为 0,那么递推后 dp 数组还是全部为 0,并且 j - nums[i] 恰好为 0,说明一个nums[i]的和就等于 j,这种方案需要 = 1 来与前面的 dp[i - 1][j] 相加来得到正确结果。
另外,滚动数组写多了转为二维数组就会遗忘两层 for 循环下还应该先进行判断,因为如果要加入的数 nums[i] 都比 j 大了,那只能继承不包含此数的方案数。
#include <iostream>
using namespace std;
const int N = 110, M = 10010;
int dp[N][M], nums[N];
int n, m;
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> nums[i];
for(int i = 0; i <= n; i++) dp[i][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(j >= nums[i])
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
else
dp[i][j] = dp[i - 1][j];
cout << dp[n][m] << endl;
return 0;
}