企业官网建设流程全解析

原题现在叫力扣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)+5=9。

底行中间的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有两种后果：

所以“加一个样例”应该有目的：非方阵专门区分行数与列数，而不只是换一组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]也会出错。测试必须能抓住已知错误，才有诊断价值。

这张旧截图不能证明博客中的循环写法正确，也不是新的性能基准。正确性理由来自状态与前驱的覆盖关系，实验负责发现实现写错的边界。