P1164

P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这是一道动态规划的经典题目，要求我们输出选取一些菜正好花完 $M$ 元。
其实动态规划和递推一样（事实上也一样），要求从局部考虑，将问题分解成选 $i$ 道菜，花完 $j$ 元，最终就能得到题目要求的个数了。
每次选一个菜的时候，有两种情况：

1. 不买这个菜，这个选择和此时还有多少钱没有关系，直接继承选了 $i-1$ 个菜时候的情况即可
2. 买这个菜，前提自然是此时有钱剩余，如果要正好用完 $M$ 元，则要在前面的 $i-1$ 个菜上用去 $j-pric{e}_i$ 元

$$\begin{array}{rl}f(i,j)& =f(i,j)+f(i-1,j),\\ f(i,j)& =f(i,j)+f(i-1,j-pric{e}_i),j\le pric{e}_i\end{array}$$

顺带提一下题解区看到的表格分析 对找状态转移方程会一些帮助吧