题目
分析
这是一道DP的题目。我们用dp[i][j]表示选到第i道菜，总价恰好为j的方案数。
状态转移就是考虑在第i道菜（对应价格prices[i]），有两种情况：
- 不选这道菜：
dp[i][j] = dp[i-1][j]。总价为j的方案完全来自前i-1道菜。 - 选这道菜：若
j >= prices[i]，则dp[i][j] += dp[i-1][j - prices[i]]。即前i-1道菜凑出j - prices[i]，再加上prices[i]，总价恰为j。 - 综合两种情形：
dp[i][j] = dp[i-1][j] + dp[i-1][j - prices[i]]（当j >= prices[i]时）。
初始条件：dp[0][0] = 1，表示考虑0道菜时总价为0的方案数为1（什么都不选）。最终答案为dp[N][M]。
答案
思考
我们用的是标准的二维DP数组。本题还可以用一维数组压缩，但需要注意凑金额时循环的方向。请读者参考上图中的代码自行思考。