Minimum Path Sum

 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     }

 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 initilize42         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 memory76         memory[i][j] = sum;77         return sum;        78     }79 }