alicode34-矩阵最小路径和

 1 package solution34;
 2 
 3 class Solution {
 4     public int solution(int[][] m) {
 5         int row = m.length;
 6         int column = m[0].length;
 7         int[][] dp = new int[row][column];
 8         dp[0][0] = m[0][0];
 9         for(int j = 1;j < column;j++){
10             dp[0][j] = dp[0][j-1] + m[0][j];
11         } 
12         for(int i=1;i<row;i++){
13             dp[i][0] = dp[i-1][0] + m[i][0];
14         }
15         for(int i=1;i<row;i++){
16             for(int j=1;j<column;j++){
17                 dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + m[i][j];
18             }
19         }
20         return dp[row-1][column-1];
21     }
22 }

算法思路：动态规划。同leetcode64 最小路径和。

先计算首行首列的值（累加和），再从[1][1]位置开始，递归计算公式为：min(dp[i-1][j],dp[i][j-1]) + m[i][j]。