1. 问题背景与核心思路

洛谷P1164"小A点菜"是一道经典的动态规划练习题，主要考察对二维DP的理解和应用。题目描述小A去餐厅点菜，菜单上有n道菜，每道菜有对应的价格。小A带了m元钱，需要计算出恰好花完m元的点菜方案数。

这道题的难点在于：

1. 需要处理"恰好花完"的条件，避免计算冗余方案
2. 要考虑不同点菜顺序是否算作不同方案（根据题意不算）
3. 需要优化空间复杂度，避免内存溢出

2. 二维DP解法详解

2.1 状态定义与转移方程

我们定义dp[i][j]表示考虑前i道菜时，花费恰好j元的方案数。状态转移方程如下：

dp[i][j] = dp[i-1][j] + (j >= price[i] ? dp[i-1][j-price[i]] : 0)

解释：

• 第一项dp[i-1][j]表示不选第i道菜时的方案数
• 第二项表示选第i道菜时的方案数（当j >= price[i]时）

2.2 初始化条件

dp[0][0] = 1 // 0道菜花费0元有1种方案（什么都不选） dp[0][j] = 0 // j>0时，0道菜无法花费j元

3. C++实现代码

#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> price(n+1); for(int i=1; i<=n; i++) cin >> price[i]; vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); dp[0][0] = 1; for(int i=1; i<=n; i++) { for(int j=0; j<=m; j++) { dp[i][j] = dp[i-1][j]; if(j >= price[i]) { dp[i][j] += dp[i-1][j-price[i]]; } } } cout << dp[n][m] << endl; return 0; }

4. 空间优化技巧

上述解法使用了O(n*m)的空间，可以进行优化：

4.1 滚动数组优化

观察到dp[i]只依赖于dp[i-1]，可以使用一维数组：

vector<int> dp(m+1, 0); dp[0] = 1; for(int i=1; i<=n; i++) { for(int j=m; j>=price[i]; j--) { dp[j] += dp[j-price[i]]; } } cout << dp[m] << endl;

注意内层循环要从后往前遍历，避免重复计算。

5. 常见问题与调试技巧

5.1 初始化错误

常见错误是忘记初始化dp[0][0]=1，导致所有结果都为0。正确的初始化是解题的关键。

5.2 边界条件处理

需要特别注意：

• 当m=0时，只有什么都不选一种方案
• 当没有任何菜可以恰好花完m元时，输出0

5.3 数据范围问题

根据洛谷题目：

• n ≤ 100
• m ≤ 10000
• 每道菜价格 ≤ 1000

使用int类型足够，不需要long long。

6. 算法复杂度分析

时间复杂度：O(n*m) 空间复杂度：

• 原始：O(n*m)
• 优化后：O(m)

对于题目给定的数据范围，两种方法都可以通过。

7. 测试用例验证

建议测试以下情况：

1. 样例输入： 4 4 1 1 2 2 输出：3
2. 边界测试： 1 0 1 输出：1
3. 无解情况： 2 5 2 2 输出：0

8. 与其他DP问题的联系

这道题与以下经典问题类似：

• 01背包问题（求最大价值）
• 硬币找零问题（求最少硬币数）
• 子集和问题（判断是否存在解）

理解这些问题的共性和区别有助于掌握DP思想。

9. 实际应用场景

这种类型的DP可以应用于：

1. 投资组合选择
2. 资源分配问题
3. 购物车优惠组合计算
4. 游戏中的装备搭配方案

10. 学习建议

对于DP初学者：

1. 先写出暴力递归解法
2. 找出重复子问题
3. 设计状态表示
4. 推导状态转移方程
5. 确定初始条件和边界情况
6. 考虑空间优化

多练习同类题目是掌握DP的最佳途径。