[Luogu] P1164 小A点菜

题目传送门

一道动态规划，\(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;
}