后端开发刷题 | 矩阵的最小路径和

描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
数据范围: 1≤n,m≤500，矩阵中任意值都满意 0≤ai,j≤100
要求：时间复杂度 O(nm)
比方：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12
，
所选择的最小累加和路径如下图所示：

[img=407

,407

]https://img-blog.csdnimg.cn/img_convert/f1b900565fd2eb7

e62fc8d83f14618d0.png[/img]

示例1

输入：

1. [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

复制代码

返回值：

1. 12

复制代码

示例2

输入：

1. [[1,2,3],[1,2,3]]

复制代码

返回值：

1. 7

复制代码

思绪分析：

该题可以使用动态规划举行求解：
创建一个比原矩阵多一行一列的二维数组temp，如许做是为了方便处理界限条件，避免在后续计算中需要特别检查是否越界。
然后对第一行和第一列举行初始化

[img=12
00,12
00]https://i-blog.csdnimg.cn/direct/86e044ecc4df4418ae2e8828a227

8f9e.png[/img]

那么取其中较小值与当前位置的值相加就是到当前位置的最小路径和，
因此状态转移公式为dp[j]=min(dp[i−1][j],dp[j−1])+matrix[j]
代码：

1. import java.util.*;
2. public class Solution {
3.     /**
4.      * @param matrix int整型二维数组 the matrix
5.      * @return int整型
6.      */
7.     public int minPathSum (int[][] matrix) {
8.         int row=matrix.length;//行
9.         int column=matrix[0].length;
10.         int[][] temp=new int[row+1][column+1];
11.         temp[0][0]=matrix[0][0];
12.         //第一行
13.         for(int i=1;i<row;i++){
14.             temp[i][0]=matrix[i][0]+temp[i-1][0];
15.         }
16.         //第一列
17.         for(int j=1;j<column;j++){
18.             temp[0][j]=matrix[0][j]+temp[0][j-1];
19.         }
21.         for(int i=1;i<row;i++){
22.             for(int j=1;j<column;j++){
23.                 if(temp[i][j-1]<temp[i-1][j]){
24.                     temp[i][j]=temp[i][j-1]+matrix[i][j];
25.                 }else{
26.                     temp[i][j]=temp[i-1][j]+matrix[i][j];
27.                 }
28.             }
29.         }
30.         return temp[row-1][column-1];
31.     }
32. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao12
3.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。