LC64—最小路径和

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

package com.nie.o2;/* * *@auth wenzhao *@date 2021/2/25 11:31 */

public class LEE64 {
   
    public int minPathSum(int[][] grid) {
   

        if (grid == null || grid.length == 0 || grid[0].length == 0) {
   
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;

        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];

        for (int i = 1; i < rows; i++) {
   
            dp[i][0] = dp[i - 1][0] + dp[i][0];
        }
        for (int i = 1; i < cols; i++) {
   
            dp[0][i] = dp[0][i - 1] + dp[0][i];
        }
        for (int i = 1; i < rows; i++) {
   
            for (int j = 1; j < cols; j++) {
   
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }

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