暴力和记忆化各调了多少次
十件小物品、容量 8。一边纯暴力递归，一边加上记忆化。运行下面这段程序： def knap_rec(items, cap, st): def go(i, c): st["t"] += 1
三种写法算得一样吗
暴力、记忆化、填表三种写法，同一批物品同一个容量。运行下面这段程序： def knap_rec(items, cap, st): def go(i, c): st["t"] += 1
第一步：先写暴力搜索
补全 knap_rec：go(i, c) 表示"从第 i 件开始挑、还剩容量 c"能拿到的最大价值。每件试"不拿"和"拿"两条路。 输出答案和调用次数。
第二步：把参数当成键存起来
补全 knap_memo：拿 (i, c) 当字典的键，进函数先查，算完先写。 输出答案和调用次数。
第三步：把递归换成填表
既然状态就是 (i, c)，那就可以不用递归了。写出一维填表版，输出容量 8 的最大价值。
⚠️ 三种写法：省了多少，答案一样吗
把三种写法都写出来，输出三样：暴力调用次数 / 记忆化调用次数 / 三个答案是否全相同（相同输出 结果一致，否则 结果不一致）。
设计状态先问自己什么
给一个新问题设计 DP 状态，要先问【0】。
交付一个进阶 DP 要验什么
把一个进阶 DP 交出去，必须验的是【0】。
五项一起对得上吗
运行下面这段程序： def knap1d(items, cap): dp = [0] * (cap + 1) for w, v in items: for c in range(cap, w - 1, -1)
第一步：两种背包
最终作品第一步：写出 0/1 背包和完全背包（同一批物品、容量 10），两个答案拼起来输出（0/1 在前）。