[LeetCode] 64. Minimum Path Sum

2024-09-06 05:08

文章标签 leetcode 64 minimum path sum

本文主要是介绍[LeetCode] 64. Minimum Path Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/minimum-path-sum/description/

题目

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[[1,3,1],[1,5,1],[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路

题目大意

求从矩阵的左上角到右下角的最小路径和，每次只能向右和向下移动。

解题思路

方法一

动态规划自顶向下，并带记录。

状态dp[i][j]：从 dp[0][0] 到 dp[i][j] 的最短路径长度。
状态初始化：dp[i][j] = Integer.MAX_VALUE，dp[0][0] = grid[0][0]
状态转移方程：dp[i][j] = Math.min(dp[i-1][j]，dp[i][j-1]) + grid[i][j]

class Solution {int [][]dp;public int getMinPath(int [][] grid,int r,int c){if(r<0 || c <0) return Integer.MAX_VALUE;if(dp[r][c]!=Integer.MAX_VALUE) return dp[r][c];dp[r][c] = Math.min(getMinPath(grid,r-1,c),getMinPath(grid,r,c-1)) + grid[r][c];return dp[r][c];}public int minPathSum(int[][] grid) {dp = new int[grid.length][grid[0].length];for(int i = 0;i<dp.length;i++)for(int j = 0 ;j<dp[0].length;j++)dp[i][j] = Integer.MAX_VALUE;dp[0][0] = grid[0][0];return getMinPath(grid,grid.length-1,grid[0].length-1);}
}

方法二

动态规划自底向上

状态dp[i][j]：从 dp[0][0] 到 dp[i][j] 的最短路径长度。
状态初始化：dp[0][0] = grid[0][0]
状态转移方程：dp[i][j] = Math.min(dp[i-1][j]，dp[i][j-1]) + grid[i][j]

class Solution {public int minPathSum(int[][] grid) {int [][]dp = new int[grid.length][grid[0].length];dp[0][0] = grid[0][0];for(int i = 1;i<dp.length;i++)  dp[i][0] = dp[i-1][0] + grid[i][0];for(int j = 1;j<dp[0].length;j++) dp[0][j] = dp[0][j-1] + grid[0][j];for(int i = 1;i<dp.length;i++)for(int j = 1 ;j<dp[0].length;j++)dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];return dp[grid.length-1][grid[0].length-1];}
}

方法三

动态规划自底向上

状态dp[j]：从 dp[0][0] 到行遍历所在 dp[j] 的最短路径长度。
状态初始化 dp[j] = dp[j - 1] + grid[i][j]，i ==0
状态转移方程：
dp[j] = dp[j] + grid[i][j]， j==0；
dp[j] = Math.min(dp[j - 1], dp[j])+ grid[i][j]，j !=0 ；
等式右边的 dp[j] 相当于上一行的dp[j],dp[j-1]是这一行的。

class Solution {public int minPathSum(int[][] grid) {int[] dp = new int[grid[0].length];dp[0] = grid[0][0];for(int j = 1;j<dp.length;j++)  dp[j] = dp[j-1]+ grid[0][j];for(int i = 1;i<grid.length;i++)for(int j =0;j<grid[0].length;j++){if(j==0)    dp[j] = dp[j] + grid[i][j];else dp[j] = Math.min(dp[j - 1], dp[j])+ grid[i][j];}return  dp[dp.length-1];}
}