LeetCode: Minimum Path Sum 解题报告

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.

SOLUTION 1:

相当基础的DP题目：

This is a simple DP.
表达式： D[i][j]: 从左下到本点的最小值
递推公式: D[i][j] = Math.mn(D[i - 1][j], D[i][j - 1]) + grid[i][j]
初始化： D[i][j] = grid[i][j].

终止条件：到达终点

 1 // Solution 1: DP
 2     public int minPathSum1(int[][] grid) {
 3         if (grid == null || grid.length == 0 || grid[0].length == 0) {
 4             return 0;
 5         }
 6         
 7         int rows = grid.length;
 8         int cols = grid[0].length;
 9         int[][] D = new int[rows][cols];
10         
11         // This is a simple DP.
12         // 表达式：  D[i][j]: 从左下到本点的最小值
13         // 递推公式: D[i][j] = Math.mn(D[i - 1][j], D[i][j - 1]) + grid[i][j]
14         // 初始化：  D[i][j] = grid[i][j].
15         for (int i = 0; i < rows; i++) {
16             for (int j = 0; j < cols; j++) {
17                 D[i][j] = grid[i][j];
18                 
19                 if (i == 0 && j != 0) {
20                     D[i][j] += D[i][j - 1];
21                 } else if (j == 0 && i != 0) {
22                     D[i][j] += D[i - 1][j];
23                 } else if (i != 0 && j != 0) {
24                     D[i][j] += Math.min(D[i][j - 1], D[i - 1][j]);
25                 }
26             }
27         }
28         
29         return D[rows - 1][cols - 1];
30     }

View Code

SOLUTION 2:

使用DFS + Memory也可以解决问题。当前到终点有2种方式，往右，往下，两种路线，取一个较小的路线就行了。

 1 public class Solution {
 2     // Solution 1: DP
 3     public int minPathSum1(int[][] grid) {
 4         if (grid == null || grid.length == 0 || grid[0].length == 0) {
 5             return 0;
 6         }
 7         
 8         int rows = grid.length;
 9         int cols = grid[0].length;
10         int[][] D = new int[rows][cols];
11         
12         // This is a simple DP.
13         // 表达式：  D[i][j]: 从左下到本点的最小值
14         // 递推公式: D[i][j] = Math.mn(D[i - 1][j], D[i][j - 1]) + grid[i][j]
15         // 初始化：  D[i][j] = grid[i][j].
16         for (int i = 0; i < rows; i++) {
17             for (int j = 0; j < cols; j++) {
18                 D[i][j] = grid[i][j];
19                 
20                 if (i == 0 && j != 0) {
21                     D[i][j] += D[i][j - 1];
22                 } else if (j == 0 && i != 0) {
23                     D[i][j] += D[i - 1][j];
24                 } else if (i != 0 && j != 0) {
25                     D[i][j] += Math.min(D[i][j - 1], D[i - 1][j]);
26                 }
27             }
28         }
29         
30         return D[rows - 1][cols - 1];
31     }
32     
33     // Solution 2: DFS + memory.
34     public int minPathSum(int[][] grid) {
35         if (grid == null || grid.length == 0 || grid[0].length == 0) {
36             return 0;
37         }
38         
39         int[][] memory = new int[grid.length][grid[0].length];
40         
41         // Bug 1: forget to initilize
42         for (int i = 0; i < grid.length; i++) {
43             for (int j = 0; j < grid[0].length; j++) {
44                 memory[i][j] = -1;
45             }
46         }
47         
48         return dfs(grid, 0, 0, memory);
49     }
50     
51     public int dfs (int[][] grid, int i, int j, int[][] memory) {
52         int rows = grid.length;
53         int cols = grid[0].length;
54         
55         if (i >= rows || j >= cols) {
56             // 表示不可达
57             return Integer.MAX_VALUE;
58         }
59         
60         // The base case: arrive the destination.
61         if (i == rows - 1 && j == cols - 1) {
62             return grid[i][j];
63         }
64         
65         // 已经搜索过的点不需要重复搜索        
66         if (memory[i][j] != -1) {
67             return memory[i][j];
68         }
69         
70         int sum = grid[i][j];
71         
72         // 开始dfs 可能的路径,目前我们只有2种可能
73         sum += Math.min(dfs(grid, i + 1, j, memory), dfs(grid, i, j + 1, memory));
74         
75         // Record the memory
76         memory[i][j] = sum;
77         return sum;        
78     }
79 }

View Code

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dp/MinPathSum_1222_2014.java