两张表各占多少格
三件物品、容量 10。二维表是 (件数+1) × (容量+1)，一维表就是 容量+1。运行下面这段程序： items = [(3, 8), (4, 9), (5, 11)] cap = 10 two = (len(items) + 1) *
两种写法算得一样吗
二维写法取 dp[3][10]，一维写法取 dp[10]。运行下面这段程序： def knap2d(items, cap): dp = [[0] * (cap + 1) for _ in range(len(items) + 1)]
把二维改成一维
下面给的是二维版。把它改写成只用一个一维数组的版本，输出容量 10 的最大价值。
答案和用掉的格子一起报
写出一维版，输出答案和这张表一共有多少格。
⚠️ 答案与空间一起摆出来
把二维版和一维版都写出来，输出四样：二维答案 / 一维答案 / 二维格子数 / 一维格子数。
区间 DP 的状态是什么
区间 DP 里 dp[i][j] 表示【0】。
⚠️ 区间 DP 的填表顺序
区间 DP 必须【0】地填表。
把四堆石子合成一堆
四堆石子 [4, 1, 2, 3]，每次只能合并相邻两堆，代价是这两堆之和。求把它们合成一堆的最小总代价。运行下面这段程序： def merge_cost(a): n = len(a) INF = 10 ** 9 p
最长回文子序列
从字符串里挑出若干字符（可以不连续，但顺序不变），要它正着读反着读一样，最长能有多长？两个例子：bbbab 和 cbbd。运行下面这段程序： def lps(s): n = len(s) dp = [[0] * n for
写石子合并
补全 merge_cost：按区间长度从 2 到 n外层循环，区间里枚举断点 k。pre 是前缀和，用来 O(1) 取区间和。