https://oi-wiki.org/dp/memo/
开个数组`mem`, 记录下来每个`dfs(pos,tleft)`的返回值。刚开始把`mem`中每个值都设成`-1`（代表没访问过）。每次刚刚进入一个 dfs 前（我们的 dfs 是递归调用的嘛），都判断`mem[pos][tleft]`是否为`-1`, 如果是就正常执行并把答案记录到`mem`中，否则？
**直接返回 mem 中的值！**
```
//
// main.cpp
// Algorithm21dynamicProgram0801
//
// Created by terry on 2021/9/3.
//
#include
**using** **namespace** std;
// C++ Version
**int** n, t;
**int** tcost\[103\], mget\[103\];
**int** mem\[103\]\[1003\];
**int** dfs(**int** pos, **int** tleft) {
**if** (mem\[pos\]\[tleft\] != -1) **return** mem\[pos\]\[tleft\];
**if** (pos == n + 1) **return** mem\[pos\]\[tleft\] = 0;
**int** dfs1, dfs2 = -1;//-INF;
dfs1 = dfs(pos + 1, tleft);
**if** (tleft >= tcost\[pos\]) dfs2 = dfs(pos + 1, tleft - tcost\[pos\]) + mget\[pos\];
**return** mem\[pos\]\[tleft\] = max(dfs1, dfs2);
}
**int** main() {
memset(mem, -1, **sizeof**(mem));
cout<<"\[t:";
cin >> t >> n;
**for** (**int** i = 1; i <= n; i++) {//for110
cout<<"\[i("<<i<<":";
cin >> tcost\[i\] >> mget\[i\];
cout<<endl;
}//for110
cout<<std::endl<<"{Dfs:";
cout << dfs(1, t) << endl;
**return** 0;
}
```
