給定一個有n個正整數(shù)的數(shù)組A和一個整數(shù)sum,求選擇數(shù)組A中部分數(shù)字和為sum的方案數(shù)壮锻。
當兩種選取方案有一個數(shù)字的下標不一樣,我們就認為是不同的組成方案娘摔。輸入描述:
輸入為兩行:
第一行為兩個正整數(shù)n(1 ≤ n ≤ 1000)，sum(1 ≤ sum ≤ 1000)
第二行為n個正整數(shù)Ai，以空格隔開。輸出描述:
輸出所求的方案數(shù)
示例1
輸入
5 15 5 5 10 2 3
輸出
4
思路
動態(tài)規(guī)劃算法。dp[i][j]表示前i個數(shù)字能夠達到和為j的方法數(shù)动遭。
然后是更新過程，首先有dp[i][j]=dp[i-1][j] （代表的是只用前面i-1個數(shù)就湊到j(luò)的方法數(shù)）神得。
之后是dp[i][j]+=dp[i-1][j-a[i]]; （表示的是加上前面i個數(shù)湊成j-a[i]的方法數(shù)厘惦，需要注意a[i] < j）
初始化時需要考慮到dp[0][0]=1，dp[0][j] = 0 ,之后的循環(huán)按照01背包的思路進行編寫哩簿。
具體代碼
#include <iostream>
using namespace std;
typedef long long LL;
int a[1234];
LL dp[1234][1234];
int n, sum;
void init() {
for (int i = 0; i <= sum; i++){
dp[0][i] = 0;
}
dp[0][0] = 1;
}
int main() {
ios::sync_with_stdio(false);
while (cin >> n >> sum) {
init();
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= a[i - 1]) dp[i][j] += dp[i - 1][j - a[i - 1]];
}
}
cout << dp[n][sum] << endl;
}
return 0;
}
