DP 要求将承载量花光的01背包问题

前言：很久没有发博客了，以后会捡起来，之后很长一段时间内我都会把精力放在攻克DP问题上，所以会经常上传一些DP学习笔记，把一些比较好的，没见过类型的DP问题都会传上来，希望能够变强吧。

因为今天很清醒的意识到世上有很多很优秀很惊艳的人，自己也要努力，努力成为那样的人啊 。

例题 洛谷P1164 小A点菜

分析：乍看就是一个普通的01背包，仔细看下要求钱是要全花完的，而且dp数组内保存的不是最大价值，而应该是方法的数量，这样处理起来是很不一样了

这道题第三次做，之前两次做都是最后无奈的屈从了题解，今天稍微看了看，就很轻松的做出来了，还是有进步的嘛。

在状态转移方程上，因为不再要求最大价值了，而且要把钱花光，所以01背包的那些max都不虚要了，用dp[i][j]表示前i种物品花j元的话，状态转移方程就是

dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]] (a[i]是一个菜花的钱数）

初始化一下：dp[0][0]=1 

然后加个滚动数组就可以了。

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1);
int a[110];
int dp[10010];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    dp[0]=1;
    for(int i=0;i<n;i++){
        for(int j=m;j>=a[i];j--)
        dp[j]=dp[j]+dp[j-a[i]];
    }
    cout<<dp[m]<<endl; 
    return 0;
}