931. 下降路径最小和 - 力扣LeetCode题目描述给你一个n x n的方形整数矩阵一条下降路径可以从第一行中的任意元素开始在每一步中可以选择下一行正下方、左下方、右下方这三个位置。要求找出一条从第一行走到最后一行的路径使得路径上所有数字之和最小返回这个最小总和。规则每一行只能选一个格子下一行列号最多偏移 ±1不能超出矩阵边界。输入matrix [[2,1,3],[6,5,4],[7,8,9]] 输出13 解释最优路径1 → 5 → 7总和 157 13解题思路状态定义dp[i][j]走到 dp 数组第i行第j列对应原矩阵matrix[i-1][j-1]时下降路径的最小总和。技巧dp 数组开成n2大小下标从1 开始左右两侧多出来的位置初始化为极大值。 好处当j1当前在第一列访问dp[i-1][j-1]会访问到左侧边界的极大值min会自动忽略这个无效位置不用额外写边界 if 判断。状态转移方程当前位置的值来自上一行三个可选位置的最小值加上当前格子的值初始化dp 数组全部初始化为INT_MAX-3减去一个数防止后续加法溢出dp[1][j] matrix[0][j-1]dp 的第一行直接等于原矩阵第一行第一行每个格子本身就是起点。结果选取终点可以是最后一行任意一列所以遍历dp[n][1] ~ dp[n][n]找出最小值返回。class Solution { public: int minFallingPathSum(vectorvectorint matrix) { int nmatrix.size(); vectorvectorintdp(n2,vectorint(n2,INT_MAX-3)); for(int i1;in1;i) { dp[1][i]matrix[0][i-1]; } for(int i2;in1;i) { for(int j1;jn1;j) { dp[i][j]min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j1]))matrix[i-1][j-1]; } } int minposINT_MAX; for(int i1;in1;i) { minposminposdp[n][i]?minpos:dp[n][i]; } return minpos; } };