[LeetCode]Dp64 最小路径和

传送门：https://leetcode-cn.com/problems/minimum-path-sum/

题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小。

说明：每次只能向下或者向右移动一步。

示例 1：
**

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

示例 2：**

输入：grid = [[1,2,3],[4,5,6]] 输出：12

解题思路：动态规划 -> 滚动数组降维

创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从(0,0)出发到 (i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0] 。
由于只能向下或者向右移动，导致 dp[i][j] 仅与 dp[i-1][j] 、dp[i][j-1] 有关

状态转移方程：

  - 当 `j=0` 时，`dp[i][0]=dp[i-1][0]+grid[i][0]`
  - 当 `i=0` 时，`dp[0][j]=dp[0][j-1]+grid[0][j]`
  - 当 `i>0,j>0` 时，`dp[i][j]=Min(dp[i][j-1]+grid[i][j],dp[i-1][j]+grid[i][j])`

复杂度分析

时间复杂度：，其中 和 分别是网格的行数和列数。
需要对整个网格遍历一次，计算 的每个元素的值。
空间复杂度：，其中 和 分别是网格的行数和列数。
创建一个二维数组 dpdp，和网格大小相同。

代码

我的代码

public class Demo {
    //动态规划,滚动数组降维优化
    public static int minPathSum_0(int[][] grid) {
        int []dp=new int[grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(j==0)
                    dp[j]=dp[j]+grid[i][j];
                else if(i==0)
                    dp[j]=dp[j-1]+grid[i][j];
                else
                    dp[j]=Math.min(dp[j]+grid[i][j],dp[j-1]+grid[i][j]);
            }
        }
        return dp[grid[0].length-1];
    }
    //动态规划,dp[i][j]代表从(0,0)到达(i,j)的最小总和
    //状态转移方程:dp[i][j]=Min(dp[i][j-1]+grid[i][j],dp[i-1][j]+grid[i][j]);
    public static int minPathSum_1(int[][] grid) {
        int[][]dp=new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        //1.预处理0行数据
        for (int i = 1; i < grid[0].length; i++) {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        //2.预处理0列数据
        for (int i = 1; i < grid.length; i++) {
            dp[i][0]=dp[i-1][0]+grid[i][0];
        }
        //3.状态转移
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                dp[i][j]=Math.min(dp[i][j-1]+grid[i][j],dp[i-1][j]+grid[i][j]);
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
    public static void main(String[] args) {
        System.out.println(minPathSum_1(new int[][]{{1,2,3},{4,5,6}}));
    }
}