【Hot100】LeetCode—64. 最小路径和

• 原题链接：64. 最小路径和

1- 思路

题目识别

• 识别1 ：给一个二维数组 grid，每次只能向下或者向右移动一步
• 识别2：求移动到右下角的最小路径和

动规五部曲

求的是路径的和，与不同路径的区别在于是否加上当前 grid[i][j] 的值

2- 实现

⭐64. 最小路径和——题解思路

class Solution {
    public int minPathSum(int[][] grid) {
        // 1. 定义 dp 数组
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[grid.length][grid[0].length];

        // 2.递推公式
        // dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);

        // 3.初始化
        dp[0][0] = grid[0][0];
        for(int i = 1 ; i < m ; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1 ; j < n ;j++){
            dp[0][j] += dp[0][j-1] + grid[0][j];
        }

        // 4.遍历
        for(int i = 1 ; i < m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        }

        return dp[m-1][n-1];
    }
}

3- ACM 实现

public class minPath {


    public static int minPathSum(int[][] grid) {
        // 1. 定义 dp 数组
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[grid.length][grid[0].length];

        // 2.递推公式
        // dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);

        // 3.初始化
        dp[0][0] = grid[0][0];
        for(int i = 1 ; i < m ; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1 ; j < n ;j++){
            dp[0][j] += dp[0][j-1] + grid[0][j];
        }

        // 4.遍历
        for(int i = 1 ; i < m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        }

        return dp[m-1][n-1];
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.substring(2,input.length()-2);
        String[] parts = input.split("],\\[");

        int[][] grid = new int[parts.length][parts[0].split(",").length];
        int rowI = 0;
        for(String str:parts){
            String[] row = str.split(",");
            for(int i = 0 ; i < row.length;i++ ){
                grid[rowI][i] = Integer.parseInt(row[i]);
            }
            rowI++;
        }

        System.out.println("结果是"+minPathSum(grid));
    }
}