64.Minimum Path Sum

Description

	#64	Minimum Path Sum	Medium
		Dynamic Programming	Top 150
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.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7

Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Solution

2D DP+DFS

Runtime 1ms		Memory 43.47MB

class Solution {
    /* 
        1 2 3
        4 5 6
        注意二维数组的计算很容易搞错
    */
    private static final int NOT_REACHABLE = 1000000;
    private int cols;
    private int rows;
    private int[][]grid;
    private int[][]dp;
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        this.cols = grid[0].length;
        this.rows = grid.length;
        this.dp = new int[rows][cols];
        for(int[] temp: dp)
            Arrays.fill(temp, NOT_REACHABLE);
        
        return findMinPath(0, 0);
    }

    private int findMinPath(int x, int y) {    
        if(x < cols && y < rows && dp[y][x] != NOT_REACHABLE){
            return dp[y][x];
        }

        if(x == cols -1 && y == rows -1) {
            return grid[y][x];
        }
        
        int current = grid[y][x];
        int min;
        if(x == cols -1) {
            // can only go down
            min = findMinPath(x, y+1);
        } else if(y == rows -1) {
            // can only go right
            min = findMinPath(x +1, y);
        } else {
            int down  = findMinPath(x, y+1);
            int right = findMinPath(x +1, y);
            min = Math.min(right, down);
        }
        return dp[y][x] = current + min;
    }
}