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;
}
```
