滾動式dp
題目是問方法數
而不是像階梯問題的路徑數
要注意
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[10010]={1};
signed main() {
int p,c,n;
while (cin>>n>>p&&n&&p) {
for (int i=1; i<=p; i++) {
dp[i]=0;
}
for (int i=0; i<n; i++) {
cin>>c;
for (int j=c; j<=p; j++) {
dp[j]+=dp[j-c];
}
}
cout<<dp[p]<<'\n';
}
}
本來送了路徑數的解法…(自己測試了WA還不信邪
我的WA code(X
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
ios::sync_with_stdio(false);
cin.tie(0);
long long dp[10001], w[100];
int n, p, i, j;
dp[0]=1;
while(cin >> n >> p and n !=0){
for(i=1;i<=p;i++){
dp[i]=0;
}
for(i=0;i<n;i++){
cin >> w[i];
}
for(i=1;i<=p;i++){
for(j=0;j<n;j++){
if(w[j]<=i){
dp[i] += dp[i-w[j]];
}
}
}
cout << dp[p] << '\n';
}
return 0;
}