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.

Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

答案

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length + 1][grid[0].length + 1];
        // Fill the two sides
        for(int i = 0; i < grid.length; i++)
            dp[i][grid[0].length] = Integer.MAX_VALUE;
        for(int i = 0; i < grid[0].length; i++)
            dp[grid.length][i] = Integer.MAX_VALUE;
        
        dp[grid.length - 1][grid[0].length - 1] = grid[grid.length - 1][grid[0].length - 1];
        for(int i = grid.length - 1; i >= 0; i--) {
            for(int j = grid[0].length - 1; j >= 0; j--) {
                if(i == grid.length - 1 && j == grid[0].length - 1) continue;
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }
        return dp[0][0];
    }
}

把代码简化，然后用滚动数组优化空间

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[2][n];
        
        int old = 0, now = 0;
        for(int i = m - 1; i >= 0; i--) {
            old = now;
            now = 1 - now;
            for(int j = n - 1; j >= 0; j--) {
                if(i == m - 1 && j == n - 1) {
                    dp[now][j] = grid[i][j];
                    continue;                    
                }
                int t = Integer.MAX_VALUE;
                if(i < m - 1) {
                    t = Math.min(t, dp[old][j]);
                }
                if(j < n - 1) {
                    t = Math.min(t, dp[now][j + 1]);
                }
                dp[now][j] = t + grid[i][j];
            }
        }
        return dp[now][0];
    }
}