洛谷P1164题解：小A点菜的动态规划解法
问题重述与基本分析
洛谷1164题描述了一个经典的点菜场景：给定n道菜的价格和m元预算，要求计算出恰好花完m元的点菜方案数。这道题本质上属于动态规划中的01背包问题变种，但与标准背包问题求最大价值不同，这里需要统计的是满足特定条件的方案数量。理解这一点是解题的关键突破口。
为什么说这是背包问题的变种呢？因为每道菜只有"点"或"不点"两种状态，对应物品的"选"与"不选"。预算m相当于背包容量，菜价就是物品重量。但常规背包求最大价值，而本题要求恰好装满背包的方案数。这种差异会导致状态转移方程的特殊处理，这也是许多初学者容易混淆的地方。
动态规划状态定义
我们定义dp[i][j]表示考虑前i道菜时，恰好花费j元的方案数。这个二维状态是解决背包类问题的典型定义。其中i的取值范围是1到n（菜品数量），j的取值范围是0到m（预算上限）。初始化时，dp[0][0] = 1表示0道菜花费0元有1种方案（即什么都不选），这是所有状态转移的基础。
状态转移需要考虑两种情况：当不选第i道菜时，方案数继承自dp[i-1][j]；当选第i道菜时，需要保证j≥当前菜价，此时方案数加上dp[i-1][j-price[i]]。这两种情况的处理体现了动态规划的无后效性特征——当前决策只依赖于前一个状态。这种分治思想正是动态规划高效解决问题的核心所在。
状态转移方程推导与优化
根据上述分析，可以写出完整的状态转移方程：dp[i][j] = dp[i-1][j] + (j >= price[i] ? dp[i-1][j-price[i]] : 0)。这个方程清晰地反映了问题的递推关系。但在实际实现时，我们发现每次迭代只用到前一行的数据，这意味着可以用滚动数组优化空间复杂度，将二维数组降为一维。
优化后的状态转移需要逆序更新：for(int j=m; j>=price[i]; j--) dp[j] += dp[j-price[i]]。为什么要逆序？因为正序更新会导致同一件物品被重复计算（完全背包问题特性），而逆序更新保证了每件物品只被考虑一次。这个细节对正确实现01背包至关重要，也是算法竞赛中常见的考察点。
案例分析与数据验证
示例测试数据：
输入：n=4, m=4, price[]={1,1,2,2}
输出：3
让我们跟踪这个案例的DP过程。初始化dp[0]=1，处理第一道菜（1元）后，dp[1]=1；处理第二道菜（1元）后，dp[2]=1；处理第三道菜（2元）时，dp[4]会加上dp[2]的值变为1；处理第四道菜（2元）时，dp[4]再次加上dp[2]的值变为3。最终dp[4]=3对应三种方案：(1+1+2)、(2+2)、(1+1+2的另一种排列)。这个案例验证了我们的算法正确性。
完整C++实现与注释
#include
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int price[n+1], dp[m+1] = {0};
for(int i=1; i<=n; i++) cin >> price[i];
dp[0] = 1; // 初始化：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]; // 输出恰好花费m元的方案数
return 0;
}本文系统性地讲解了洛谷1164题的解题思路，从问题分析、状态定义到方程推导和优化实现。通过这个典型例题，我们不仅学会了如何解决特定背包问题变种，更重要的是掌握了动态规划解决组合优化问题的通用方法。记住，理解状态转移的本质比记忆模板更重要，这是提升算法能力的关键。建议读者尝试用类似思路解决洛谷其他背包变种题目，如P1048（采药）、P1060（开心的金明）等，以巩固学习效果。
原创内容 转载请注明出处
