矩阵的最小路径和算法

矩阵的最小路径和算法

题目描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
示例1
输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值：12

解题思路

先把矩阵数组列出来，方便好理解：
[1,3,5,9]
[8,1,3,4]
[5,0,6,1]
[8,8,4,0]
题目中说从最左上的元素到达最右下的元素只能通过右走或者往下走，一开始我以为可以通过贪心算法，从最左上元素出发，选择右边或下边两个最小的元素相加，然后循环此步骤，但后来发现不对，因为是全局的最短路径，这里的贪心算法就算走到最右下的位置，也不能代表全局最短，只能表明当前最短。
因此换个思路，既然是全局最短，而且对于每个元素来说，只有他的上边或者左边的位置能到达它，因此我们只要求出最右下的左边和上边元素最小的那个元素a，而最小的那个元素a又需要求出它的左边和上边元素最小的那个，这样分析就有点动态规划的意思了，可以列出公式：
d[i][j]=d[i][j]+min(d[i-1][j],d[i][j-1])
我们需要求出所有元素的累加值，然后最后选d[i][j]的值即是最终结果。
而矩阵数组的第一行只能通过左边的元素累加，第一列只能通过上边的元素累加，因此先求出第一行和第一列的累加值，后续就可以相应地遍历进行累加。

代码实现

import java.util.*;public class Solution {/*** [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]* @param matrix int整型二维数组 the matrix* @return int整型*/public int minPathSum (int[][] matrix) {int m=matrix.length;int n=matrix[0].length;//给第一列的每个元素算出最短路径和for(int i=1;i<m;i++){matrix[i][0]=matrix[i-1][0]+matrix[i][0];            }//给第一行的每个元素算出最短路径和for(int i=1;i<n;i++){matrix[0][i]=matrix[0][i-1]+matrix[0][i];            }for(int i=1;i<m;i++){for(int j=1;j<n;j++){matrix[i][j]=matrix[i][j]+Math.min(matrix[i][j-1],matrix[i-1][j]);    }}return matrix[m-1][n-1];}}