---

题目

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

---

1- 思路

• 不同的路径 ——> 多维 dp ——> 每次只能向下或者向右一步 ——> 动规五部曲 两个方向定义递推公式

---

2- 实现

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

class Solution {public int minPathSum(int[][] grid) {// 1. 定义 dp 数组int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];// 2. 递推公式// dp[i][j] += Math.min(grid[i-1][j],grid[i][j-1]);// 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] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);}}return dp[m-1][n-1];}
}

---

3- ACM 实现

public class minPathSum {public static int minPath(int[][] grid){int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];// 2. 递推公式// dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);// 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] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);}}return dp[m-1][n-1];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组行数 m ");int m = sc.nextInt();System.out.println("输入数组列数 n ");int n = sc.nextInt();int[][] grid = new int[m][n];for(int i = 0 ; i < m;i++){for(int j = 0 ; j < n ; j++){grid[i][j] = sc.nextInt();}}System.out.println("结果是"+minPath(grid));}
}