目录
- 1- 思路
- 题目识别
- 动规五部曲
- 2- 实现
- ⭐64. 最小路径和——题解思路
- 3- ACM 实现
- 原题链接: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));}
}