转载

[原]LeetCode Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

思路分析:这题是MSRA面试遇到过的原题，可见IT公司面试刷题太重要太重要。如果做过类似的dp题目就会觉得这题非常简单，几乎可以5分钟秒掉。这题和Unique PathsUnique Paths II是同类型的题目，类似的dp套路，由于每个格子的入口只有左边相邻和上边相邻的格子，定义数组dp[m][n]令dp[i][j]表示从起点到(i,j)的最短路径和（稍微变形也可以改成最大路径和），容易得到dp递推式 dp[i][j] = grid[i][j] + min{dp[i-1][j], dp[i][j-1]}，有了递推式，实现就非常容易了，就是不断填二维数组，两个for循环搞定。但是这题空间上还可以进一步优化，因为只需要使用相邻上一行dp数组的信息，也可以定义一维数组dp来做，严谨的做法是如果是m行n列，就取m n中较小的定义dp数组。这里给出的实现是O（n）空间的解法，定义一维dp数组保存相邻上一行信息递归计算。

AC Code

使用O（m*n）空间的版本

public int minPathSum(int[][] grid) {  //0911  int m = grid.length;  if(m == 0) return 0;  int n =  grid[0].length;  int [][] dp = new int [m][n];  dp[0][0] = grid[0][0];  for(int i = 1; i < m; i++){   dp[i][0] = dp[i-1][0] + grid[i][0];  }  for(int j = 1; j < n; j++){   dp[0][j] = dp[0][j-1] + grid[0][j];  }  for(int i = 1; i < m; i++){   for(int j = 1; j < n; j++){    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];   }  }  return dp[m-1][n-1]; }

使用O（n）空间的版本，还可以进一步优化，取m和n中较小的一个定义dp数组，空间复杂度为O（min(m,n)）

public int minPathSum(int[][] grid) {  //0932  int m = grid.length;  if(m == 0) return 0;  int n = grid[0].length;  int [] dp = new int[n];  dp[0] = grid[0][0];  for(int j = 1; j < n; j++){   dp[j] = dp[j-1] + grid[0][j];  }  for(int i = 1; i < m; i++){   for(int j = 0; j < n; j++){    if(j == 0){     dp[j] += grid[i][j];    } else {     dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);    }   }  }  return dp[n-1];  //0942 }

正文到此结束