嘿，你找对路子了——这个从(0,0)到(n,n)仅能向右/向下移动的最大路径和问题，**制表法（迭代式动态规划）**就是最标准、高效的实现方案，完全避开了递归的重复计算问题，空间上也能做到很紧凑。我来给你一步步拆解：

核心思路 #

我们用一个二维表格（甚至可以直接复用原网格节省空间）来存储「从起点(0,0)走到当前位置(i,j)的最大路径和」，通过填充这个表格的边界和内部状态，最终直接读取终点的数值就能得到答案。

具体步骤 #

1. 定义状态 #

设dp[i][j]表示从(0,0)走到网格中第i行第j列位置时，能获得的最大路径和。

2. 初始化边界 #

因为只能向右或向下走，所以第一行的所有位置只能从左边一步步过来，第一列的所有位置只能从上方一步步过来：

• 第一行：dp[0][j] = dp[0][j-1] + grid[0][j]（j从1开始）
• 第一列：dp[i][0] = dp[i-1][0] + grid[i][0]（i从1开始）
• 起点dp[0][0]直接等于原网格的grid[0][0]

3. 填充内部表格 #

对于不在边界的位置(i,j)，我们可以选择从上方(i-1,j)或者左方(i,j-1)走过来，取这两个方向的最大路径和，再加上当前网格的数值：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

4. 获取结果 #

填充完整个表格后，dp[n][n]就是从(0,0)到(n,n)的最大路径和。

结合你的输入示例演示 #

你的输入是5 1 2 6 7 8 1 4 9，对应3x3网格（n=2）：

grid = [
    [5, 1, 2],
    [6, 7, 8],
    [1, 4, 9]
]

按照步骤计算：

1. 初始化边界：
   • 第一行：dp[0][0]=5，dp[0][1]=5+1=6，dp[0][2]=6+2=8
   • 第一列：dp[1][0]=5+6=11，dp[2][0]=11+1=12
2. 填充内部：
   • dp[1][1] = max(6,11) +7 = 18
   • dp[1][2] = max(8,18) +8 =26
   • dp[2][1] = max(18,12)+4=22
   • dp[2][2] = max(26,22)+9=35
     最终结果就是35，和你的示例输出一致。

空间优化小技巧 #

如果不想额外开辟dp数组，可以直接在原网格上修改——因为每个位置的数值只需要用到上方和左方的旧值，修改后不会影响后续计算。这样空间复杂度可以从O(n²)降到O(1)（只复用原空间）。

完整代码示例（Python） #

def max_path_sum(grid):
    n = len(grid) - 1  # 因为是(n,n)终点，网格边长是n+1
    # 初始化第一行
    for j in range(1, n+1):
        grid[0][j] += grid[0][j-1]
    # 初始化第一列
    for i in range(1, n+1):
        grid[i][0] += grid[i-1][0]
    # 填充内部
    for i in range(1, n+1):
        for j in range(1, n+1):
            grid[i][j] += max(grid[i-1][j], grid[i][j-1])
    return grid[n][n]

# 测试你的输入示例
input_grid = [[5,1,2],[6,7,8],[1,4,9]]
print(max_path_sum(input_grid))  # 输出35

这个解法不管是时间复杂度（O(n²)，每个位置只计算一次）还是空间复杂度都非常高效，完全适配这类网格路径问题的需求。

内容的提问来源于stack exchange，提问作者Marzouk