一、递推思路：
以中间某个通过状态为样本进行分析，比如我们现在面对第(i)种菜，设(f[i])是前(i)种菜的所有点菜方法，但仔细一想，这样不行，为什么呢？因为只考虑了菜，没考虑钱！不考虑钱的点菜是没有灵魂的~
所以前(i)种菜的点菜方法，是受钱数制约的，就是，还有另一个钱数的维度。所以，我们设(f[i][j])给在前(i)种菜，在钱数上限(j)之内的点菜方法数。
注意：
本题是二维的，与前一题P2437 蜜蜂路线不一样，那个简单，是一维的。
(f[i][j])是由哪些状态转移而来呢？我们可以想像，我们面对第(i)个菜，有三种情况：
一、剩余的钱数正好等于(i)号菜价格
1、选择购买,买完了就没有钱了，就到头了。加(1)就完事了,游戏到此结束啊！！也可以理解为(base case),就是基础依赖项，开头项。
(f[i][j]=f[i-1][j]+1)
2、不选择就是原来的。(f[i][j]=f[i-1][j])
二、剩余的钱数大于购买(i)号菜价格
1、选择购买
(f[i][j]=f[i-1][j-a[i]])
2、不选择就是原来的。(f[i][j]=f[i-1][j])
三、剩余的钱数小于购买第(i)号菜价格
1、没的选，只能是(f[i][j]=f[i-1][j])
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int M = 10010;
int a[N], f[N][M];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i)cin >> a[i];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
//正好相等，方案数+1
if (j == a[i])f[i][j] = f[i - 1][j] + 1;
//如果大于，不选，就是原来的方案数；选了，那么就依赖于j-a[i]这些钱在i-1个物品中的方案数
if (j > a[i]) f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]];
//如果小于，没的选择
if (j < a[i]) f[i][j] = f[i - 1][j];
}
cout << f[n][m];
return 0;
}
二、递归思路
有时，递归与深度优先我喜欢混淆概念，因为从本质上讲，深度优先就是递归嘛。
深搜的话，就是一样一个思路：
1、我一个都没点菜，兜里有钱(m)元。
2、我看了一眼第一个菜，存在三种可能：
（1）等于(m)元
如果点了，则钱花光，方法数+1；
如果不点，继续下一个菜。
（2）大于(m)元
如果点了，则钱减少；继续点下一个菜。
如果不点，则继续点下一个菜。
（3）小于(m)元
不够买，只能放弃。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int n, m;
//纯递归思路，最后一个测试点TLE
//x:第几个位置
//m:钱数上限
int dfs(int x, int m) {
int ans = 0;
if (m == 0) return 1;//钱花光，增加一种办法
if (x == n) return 0;//选择完n种，钱还没有花光，无效方法
//看下一个菜，如果钱还够
if (a[x + 1] <= m)
ans += dfs(x + 1, m - a[x + 1]); //选择当前位置的菜
ans += dfs(x + 1, m); //不选择当前位置的菜
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
cout << dfs(0, m) << endl;
return 0;
}
因为递归会存在大量重复计算，所以可以采用记忆化的方法记录到二维数组中，减少计算次数：
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int n, m;
int dp[N][10010];
//x:第几个位置
//m:钱数上限
int dfs(int x, int m) {
if (dp[x][m]) return dp[x][m];
int ans = 0;
if (m == 0) return 1;
if (x == n) return 0;
if (a[x + 1] <= m) ans += dfs(x + 1, m - a[x + 1]); //选择当前位置的菜
ans += dfs(x + 1, m); //不选择当前位置的菜
dp[x][m] = ans;
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
cout << dfs(0, m) << endl;
return 0;
}