题目：
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.
链接：
题解：
DP，可以in-place，也可以使用滚动数组。
Time Complexity - O(mn)， Space Complexity - O(1)。
public class Solution { public int minPathSum(int[][] grid) { if(grid == null || grid.length == 0) return 0; for(int i = 1; i < grid.length; i ++){ grid[i][0] += grid[i - 1][0]; } for(int j = 1; j < grid[0].length; j ++){ grid[0][j] += grid[0][j - 1]; } for(int i = 1; i < grid.length; i ++){ for(int j = 1; j < grid[0].length; j ++){ grid[i][j] += Math.min(grid[i][j - 1], grid[i - 1][j]); } } return grid[grid.length - 1][grid[0].length - 1]; }}
Update:
public class Solution { public int minPathSum(int[][] grid) { if(grid == null || grid.length == 0) return 0; int rowLen = grid.length, colLen = grid[0].length; for(int i = 1; i < rowLen; i++) //initialize first column grid[i][0] += grid[i - 1][0]; for(int j = 1; j < colLen; j++) //initialize first row grid[0][j] += grid[0][j - 1]; int sum = 0; for(int i = 1; i < rowLen; i++) { for(int j = 1; j < colLen; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[rowLen - 1][colLen - 1]; }}
二刷：
依然是dp，跟前两道题一样。
Java:
Time Complexity - O(mn)， Space Complexity - O(1)。
public class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rowNum = grid.length, colNum = grid[0].length; for (int i = 1; i < rowNum; i++) { grid[i][0] += grid[i - 1][0]; } for (int j = 1; j < colNum; j++) { grid[0][j] += grid[0][j - 1]; } for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[rowNum - 1][colNum - 1]; }}
题外话：
1/31/2016
这几天头有点昏，做题速度较慢。其实这一个月都很慢，按照计划应该完成了150题才对，结果到现在为止也才60题，差得太多了。
现在是8点，我在犹豫要不要去吃半亩园。9点钟关门， 开车过去大概20分钟的样子。下午刚跑完步，晚上来一顿估计就白跑了 -____-!! 纠结啊
三刷:
Java:
Time Complexity - O(mn)， Space Complexity - O(n)。 m为行数，n为列数
public class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0) return Integer.MIN_VALUE; int rowNum = grid.length, colNum = grid[0].length; for (int i = 1; i < rowNum; i++) grid[i][0] += grid[i - 1][0]; for (int j = 1; j < colNum; j++) grid[0][j] += grid[0][j - 1]; for (int i = 1; i < rowNum; i++) { for (int j = 1; j < colNum; j++) { grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[rowNum - 1][colNum - 1]; }}
Update:
使用滚动数组。
Java:
public class Solution { public int minPathSum(int[][] grid) { if (grid == null || grid.length == 0) return 0; int rowNum = grid.length, colNum = grid[0].length; int[] dp = new int[colNum]; dp[0] = grid[0][0]; for (int j = 1; j < colNum; j++) dp[j] = grid[0][j] + dp[j - 1]; for (int i = 1; i < rowNum; i++) { dp[0] += grid[i][0]; for (int j = 1; j < colNum; j++) { dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]); } } return dp[colNum - 1]; }}
