算法题下降路径最小和-深圳市維司達科技有限公司

931. 下降路径最小和

问题描述

给你一个n x n的方形整数数组matrix，请你找出并返回通过matrix的下降路径的最小和。

下降路径的定义：

从第一行的任意元素开始
每一步可以移动到下一行的相邻列（即列号为j-1、j或j+1，但不能超出边界）
到达最后一行结束

示例：

输入: matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出: 13 解释: 最小下降路径为 [1,4,8]，和为13。 输入: matrix = [[-19,57],[-40,-5]] 输出: -59 解释: 最小下降路径为 [-19,-40]，和为-59。

算法思路

动态规划（自底向上）：

状态定义：

dp[i][j]表示从位置(i, j)到最后一行的最小下降路径和

状态转移方程：

对于最后一行：dp[n-1][j] = matrix[n-1][j]
对于其他行：dp[i][j] = matrix[i][j] + min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1])
需要处理边界情况（j-1 >= 0且j+1 < n）

代码实现

方法一：动态规划

classSolution{/** * 计算下降路径的最小和 * * @param matrix n x n 的整数矩阵 * @return 下降路径的最小和 */publicintminFallingPathSum(int[][]matrix){intn=matrix.length;if(n==1)returnmatrix[0][0];// dp[i][j] 表示从(i,j)到最后一行的最小下降路径和int[][]dp=newint[n][n];// 初始化最后一行for(intj=0;j<n;j++){dp[n-1][j]=matrix[n-1][j];}// 自底向上填充DP表for(inti=n-2;i>=0;i--){for(intj=0;j<n;j++){// 找到下一行中相邻列的最小值intminNext=dp[i+1][j];// 正下方// 左下方（如果存在）if(j>0){minNext=Math.min(minNext,dp[i+1][j-1]);}// 右下方（如果存在）if(j<n-1){minNext=Math.min(minNext,dp[i+1][j+1]);}dp[i][j]=matrix[i][j]+minNext;}}// 找到第一行中的最小值intresult=dp[0][0];for(intj=1;j<n;j++){result=Math.min(result,dp[0][j]);}returnresult;}}

方法二：滚动数组

classSolution{/** * 使用滚动数组 */publicintminFallingPathSum(int[][]matrix){intn=matrix.length;if(n==1)returnmatrix[0][0];// 只需要保存下一行的结果int[]nextRow=newint[n];int[]currentRow=newint[n];// 初始化最后一行for(intj=0;j<n;j++){nextRow[j]=matrix[n-1][j];}// 自底向上计算for(inti=n-2;i>=0;i--){for(intj=0;j<n;j++){intminNext=nextRow[j];if(j>0){minNext=Math.min(minNext,nextRow[j-1]);}if(j<n-1){minNext=Math.min(minNext,nextRow[j+1]);}currentRow[j]=matrix[i][j]+minNext;}// 交换数组引用int[]temp=nextRow;nextRow=currentRow;currentRow=temp;}// nextRow 现在包含第一行的结果intresult=nextRow[0];for(intj=1;j<n;j++){result=Math.min(result,nextRow[j]);}returnresult;}}

方法三：自顶向下递归 + 记忆化

classSolution{privateint[][]memo;privateint[][]matrix;privateintn;/** * 自顶向下递归 + 记忆化 */publicintminFallingPathSum(int[][]matrix){this.matrix=matrix;this.n=matrix.length;if(n==1)returnmatrix[0][0];this.memo=newint[n][n];for(inti=0;i<n;i++){Arrays.fill(memo[i],Integer.MAX_VALUE);}intresult=Integer.MAX_VALUE;// 从第一行的每个位置开始for(intj=0;j<n;j++){result=Math.min(result,dfs(0,j));}returnresult;}/** * 递归函数：计算从(i,j)开始的最小下降路径和 */privateintdfs(inti,intj){// 边界检查if(i>=n||j<0||j>=n){returnInteger.MAX_VALUE;}// 到达最后一行if(i==n-1){returnmatrix[i][j];}// 记忆化if(memo[i][j]!=Integer.MAX_VALUE){returnmemo[i][j];}// 递归计算三个方向intleft=dfs(i+1,j-1);intdown=dfs(i+1,j);intright=dfs(i+1,j+1);intminNext=Math.min(Math.min(left,down),right);memo[i][j]=matrix[i][j]+minNext;returnmemo[i][j];}}

算法分析

方法	时间复杂度	空间复杂度
DP	O(n²)	O(n²)
滚动数组	O(n²)	O(n)
记忆化递归	O(n²)	O(n²)

算法过程

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]

方法一：

初始化最后一行：dp[2] = [7,8,9]
计算第1行：
- dp[1][0] = 6 + min(7,8) = 13
- dp[1][1] = 5 + min(7,8,9) = 12
- dp[1][2] = 4 + min(8,9) = 12
计算第0行：
- dp[0][0] = 2 + min(13,12) = 14
- dp[0][1] = 1 + min(13,12,12) = 13
- dp[0][2] = 3 + min(12,12) = 15
结果：min(14,13,15) = 13

输入：matrix = [[-19,57],[-40,-5]]

dp[1] = [-40,-5]
dp[0][0] = -19 + (-40) = -59
dp[0][1] = 57 + min(-40,-5) = 52
结果：min(-59,52) = -59

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[][]matrix1={{2,1,3},{6,5,4},{7,8,9}};System.out.println("Test 1: "+solution.minFallingPathSum(matrix1));// 13// 测试用例2：负数int[][]matrix2={{-19,57},{-40,-5}};System.out.println("Test 2: "+solution.minFallingPathSum(matrix2));// -59// 测试用例3：单元素int[][]matrix3={{5}};System.out.println("Test 3: "+solution.minFallingPathSum(matrix3));// 5// 测试用例4：全负数int[][]matrix4={{-1,-2,-3},{-4,-5,-6},{-7,-8,-9}};System.out.println("Test 4: "+solution.minFallingPathSum(matrix4));// -18// 测试用例5：全正数int[][]matrix5={{1,2,3},{4,5,6},{7,8,9}};System.out.println("Test 5: "+solution.minFallingPathSum(matrix5));// 12// 测试用例6：大数值int[][]matrix6={{100,200,300},{400,500,600},{700,800,900}};System.out.println("Test 6: "+solution.minFallingPathSum(matrix6));// 1200// 测试用例7：混合正负int[][]matrix7={{1,-1,1},{-1,1,-1},{1,-1,1}};System.out.println("Test 7: "+solution.minFallingPathSum(matrix7));// -1// 测试用例8：4x4矩阵int[][]matrix8={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};System.out.println("Test 8: "+solution.minFallingPathSum(matrix8));// 28}