【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));}
}