01 背包

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

DFS + 记忆化

最常规的做法，从头开始搜索，每个 pos 都有两种选择，要么采这棵药草（加上时间和不超时），要么不采。

二维 DP

每种情况可以表示为 $dp(i,j)$，以 $j$ 为容量放入前 $i$ 个物品。 所谓 DP，就是计算对于某个实际问题所有可能条件下的问题答案，这个答案可以由之前的情况推出。 某篇题解认为的 DP 是自底向上而记忆化搜索时自上向底再回溯是非常完美的形容。 通过 DP 计算出了所有可能值自然也能找到我们想要的值了。[[动态规划]]

基本情况

1. $i=1$，此时必定放入唯一的物品，一定是最优解；

转移方程

再考虑 $j$ 不足选择的情况，自然是不选，此时的最大值自然和上一个状态相同。 这个转移方程显然是正确的，只要保证每一轮都取局部最大值，就能推导出整体的最大值，符合最优子结构性质。

一维 DP