原题现在叫力扣LCR 166珠宝的最高价值。从矩形网格的左上角出发每次只能向右或向下走到右下角沿途价值相加求最大值。原笔记使用“礼物”的叫法下面沿用。我原来的入口是定义“走到这一格”的状态而不是先背一个max公式。这个思路正确但原文Java代码把内层列数写成了行数j m。3×3样例看不出来长方形会出问题。这次先讲清状态再用长方形检查实现。1. 为什么不是每一步选旁边更贵的礼物看看这个网格1 9 1 8 1 1 100 1 1起点右边9比下边8贵。如果只看下一步就先往右之后再怎么走也回不到左下角的100最多拿到13。先向下、再向下的路径却能拿到111。下一格值大不代表后面的整条路更好。动态规划不做这个局部决定。它问假如已经走到某个位置到这里为止最多能拿多少2. 到这里之前最后一步只能来自两个地方定义best[i][j]为从左上角走到原网格(i,j)时的最大价值包含当前格子的价值。best[i-1][j] | v best[i][j-1] -- grid[i][j]到达内部格子最后一步要么来自上面要么来自左边。这两种情况覆盖了全部合法路径。来自同一前驱的路径为什么只保留价值最高的一条因为到了同一格后后续可走的格子完全一样。累计价值较低的路径接上同一段后缀也追不上较高的路径。所以内部格子的转移是best[i][j] max(best[i-1][j], best[i][j-1]) grid[i][j]注意grid[i][j]是当前礼物的值best[i][j]是一条路径的累计值不能把两个量混在一起。3. 把样例填完整不只写公式原网格与累计价值表原网格 best表 1 3 1 1 4 5 1 5 1 2 9 10 4 2 1 6 11 12中心的5上面累计是4左边累计是2因此这里为max(4,2)59。底行中间的2上面累计是9左边累计是6因此这里为11。终点的1上面累计是10左边累计是11因此结果12。一条最优路径是1→3→5→2→1。DP表中的每个数代表“到这一格的最优值”不是说所有格子都属于同一条路径。4. 原图里的辅助行、辅助列是什么图里左侧红色箭头表示逐行填表右侧额外加了一行和一列0。紫色线是一次路径标记不能把图中尚未填完整的格子当作最终DP表完整数值以上一节为准。代码多开一行和一列让dp[i][j]对应原网格grid[i-1][j-1]。这样第一行和第一列也能直接写同一个转移。为什么额外的位置能是0这与题目的非负价值有关沿有效边界累计的值不会小于0虚拟位置不会带来更好的非法入口。起点则得到max(0,0)grid[0][0]。如果把题改成允许负值不能照搬这套0边界。例如单行[-5,-1]第二格会错误地从上面的0“进入”得到-1而真实路径必须拿到-6。那时应单独初始化起点、首行和首列或用明确的不可达状态。5. Java实现行数和列数各管各的class Solution { public int jewelleryValue(int[][] grid) { int m grid.length; int n grid[0].length; int[][] dp new int[m 1][n 1]; for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]) grid[i - 1][j - 1]; } } return dp[m][n]; } }从上到下、从左到右填表保证上方和左方先算好。网格非空且为矩形是输入前提这不是处理任意锯齿数组的通用API。时间为O(mn)额外空间为O(mn)。这里沿用原Java的int接口如果自行扩展价值范围必须确认路径总和能放进int否则累计表与返回类型应改用long不能只看每格都在int范围内。原代码的j m有两种后果输入正确结果原错误循环的表现[[1,2,3],[4,5,6]]16只填两列终点第三列仍为0[[1,2],[3,4],[5,6]]15尝试访问第三列越界所以“加一个样例”应该有目的非方阵专门区分行数与列数而不只是换一组3×3数字。6. 想压空间先看哪些旧值还要用这一步不是解题必须。当前格只依赖上一行的同列、当前行的左列所以可以保留一行数组class RollingSolution { public int jewelleryValue(int[][] grid) { int n grid[0].length; int[] dp new int[n 1]; for (int[] row : grid) { for (int j 1; j n; j) { dp[j] Math.max(dp[j], dp[j - 1]) row[j - 1]; } } return dp[n]; } }更新前dp[j]还是上一行dp[j-1]已更新成当前行。因此必须从左往右。空间变成O(n)时间不变不修改输入网格。7. 验证不是用另一张DP表互相对答案本地对照程序枚举小网格所有只能向右、向下的完整路径直接累计每条路径取最大值。它不使用DP转移适合检查两份实现。测试包括1×1、单行、单列、两种长方形、题目样例、上述局部贪心反例再穷举1至3行、1至3列、每格取1或2的所有网格并加入固定种子的随机长方形。额外用200×200全1网格检查大尺寸答案是399。还运行备份中的原代码确认长方形分别触发“返回0”和“越界”。滚动数组故意改成从右往左扫描时单行[1,2,3]也会出错。测试必须能抓住已知错误才有诊断价值。这张旧截图不能证明博客中的循环写法正确也不是新的性能基准。正确性理由来自状态与前驱的覆盖关系实验负责发现实现写错的边界。