方法五当中的背包那个思路,我自己想的时候,只改了j的范围,然后全wa了,当改成1就过了,这是什么原因呢?
#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000007;
typedef long long ll;
int n,m,a[105];
int dp[105];
int ans=-1;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=1;k<=min(j,a[i]);k++){
//这种花最多放几盆
dp[j]=(dp[j]+dp[j-k])%mod;
}
}
}
cout<<dp[m]<<endl;
return 0;
}