动态规划之最小路径和

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解析1(二维数组法)：假设dp[i][j]是从ij点到最右下角元素的最小路径，那么dp[j][j]=min(dp[i+1][j],dp[i][j+1])+当前元素.
时间复杂度 ：O(mn)O(mn)。遍历整个矩阵恰好一次。
空间复杂度 ：O(mn)O(mn)。额外的一个同大小矩阵。

public class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        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)//最下一行，但不是最右下角元素
                    dp[i][j] = grid[i][j] +  dp[i][j + 1];//只有一种路径方法
                else if(j == grid[0].length - 1 && i != grid.length - 1)//最右一行，但不是最右下角元素
                    dp[i][j] = grid[i][j] + dp[i + 1][j];//只有一种路径方法
                else if(j != grid[0].length - 1 && i != grid.length - 1)//其他
                    dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                else//最右下角元素
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
}

解析2(二维数组):与上述相比区别在于，直接在愿数组上进行更新，不需要额外的空间复杂度。
时间复杂度 ：O(mn)O(mn)。遍历整个矩阵恰好一次。
空间复杂度 ：O(1)O(1)。不需要额外空间。

public class Solution {
    public int minPathSum(int[][] grid) {
        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)
                    grid[i][j] = grid[i][j] +  grid[i][j + 1];
                else if(j == grid[0].length - 1 && i != grid.length - 1)
                    grid[i][j] = grid[i][j] + grid[i + 1][j];
                else if(j != grid[0].length - 1 && i != grid.length - 1)
                    grid[i][j] = grid[i][j] + Math.min(grid[i + 1][j],grid[i][j + 1]);
            }
        }
        return grid[0][0];
    }
}

解析3(一维数组):假设dp[j],j的长度为列数，我们只需要更新dp[],dp[0]即为所求。
时间复杂度 ：O(mn)O(mn)。遍历整个矩阵恰好一次。
空间复杂度 ：O(n)O(n)。额外的一维数组，和一行大小相同。

public class Solution {
   public int minPathSum(int[][] grid) {
       int[] dp = new int[grid[0].length];
       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)//最下一行，但不是最右下角元素
                   dp[j] = grid[i][j] +  dp[j + 1];//只有一种路径方法
               else if(j == grid[0].length - 1 && i != grid.length - 1)//最右一行，但不是最右下角元素
                   dp[j] = grid[i][j] + dp[j];//也只有一种路径方法
               else if(j != grid[0].length - 1 && i != grid.length - 1)//其他
                   dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);//
               else//最右下角元素
                   dp[j] = grid[i][j];
           }
       }
       return dp[0];
   }
}