这种的动态规划题目主要还是不能被自己的思路限制了，之前的dp[i][j]是“最大值”；这里得把dp[i][j]理解为前i个物品放到j容的背包中的方法；那么很显然有递推公式：代码：#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<stri

原题链接：https://www.luogu.com.cn/problem/P1164题意解读：要求正好把钱花完，并且统计不同的点菜方案数，本质上是一个背包问题，给定背包体积，要求物品正好装满背包的方案数。解题思路：1、最直观的解法是暴搜：DFS枚举每一道菜，有点或者不点两种选择，并且累加上已花费的总金额递归前，判断

题目传送门一道动态规划，\(dp_{i, j}\)表示用前\(i\)个菜品花光\(j\)元的方法总数那么可以推出状态转移方程：\(if(j>a_i)\spacedp_{i,j}=dp_{i-1,j}+dp_{i-1,j-a_{i}}\)如果j比ai大，那么方案数就是不买\(dp_{i − 1, j}\)+买\(dp_{i − 1, j − a_i}\)，其中如果买，那么