一道动态规划，\(dp_{i, j}\)表示用前\(i\)个菜品花光\(j\)元的方法总数
那么可以推出状态转移方程：
- \(if(j>a_i)\space dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-a_{i}}\)
如果j比ai大，那么方案数就是不买\(dp_{i − 1, j}\)+买\(dp_{i − 1, j − a_i}\)，其中如果买，那么第\(i\)件物品就要是\(j − a_i\)元，即\(dp_{i − 1, j − a_i}\)
- \(if(j=a_i)\space dp_{i,j}=dp_{i-1,j}+1\)
如果刚刚好，那么\(dp_{i, j}\)就是\(dp_{i − 1, j} + 1\)
- \(if(j<a_i)\space dp_{i,j}=dp_{i-1,j}\)
如果买不了，那么方案数就沿袭\(dp_{i − 1, j}\)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[110],dp[110][10010];
//dp[i][j]为用前i道菜花光j元的方法总数
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j<a[i]) dp[i][j]=dp[i-1][j];
else if(j==a[i]) dp[i][j]=dp[i-1][j]+1;
else dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
}
}
cout<<dp[n][m];
// system("echo= & pause");
return 0;
}