方法数

出自问题: P1164 小A点菜 P1077 [NOIP2012 普及组] 摆花(该题略有这个思想)

说明

开个玩笑，这是一道简单的动规题，定义f[i][j]为用前i道菜用光j元钱的办法总数，其状态转移方程如下：

（1）if(j==第i道菜的价格)f[i][j]=f[i-1][j]+1;

（2）if(j>第i道菜的价格) f[i][j]=f[i-1][j]+f[i-1][j-第i道菜的价格];

（3）if(j<第i道菜的价格) f[i][j]=f[i-1][j];

说的简单一些，这三个方程，每一个都是在吃与不吃之间抉择。若钱充足，办法总数就等于吃这道菜的办法数与不吃这道菜的办法数之和；若不充足，办法总数就只能承袭吃前i-1道菜的办法总数。依次递推，在最后，我们只要输出f[n][m]的值即可。

对于此处的 if(j>第i道菜的价格) 解释

DP[i][j] = DP[i - 1][j] + DP[i - 1][j - arr[i]]

其中，DP[i - 1][j] 表示不购买第 i 道菜时，用 j 元钱点前面 i - 1 道菜的方案数；

DP[i - 1][j - arr[i]] 表示购买第 i 道菜时，用 $剩余$ 的钱（j - arr[i]）点前面 i - 1 道菜的方案数。