本文主要是介绍稀碎从零算法笔记Day51-LeetCode:最小路径和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题型:DP、数组、矩阵
链接:64. 最小路径和 - 力扣(LeetCode)
来源:LeetCode
题目描述
给定一个包含非负整数的 m x n
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
题目样例
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]] 输出:12
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
题目思路
①全局最优,DP ②找到最短的路径,可以BFS
矩阵,可以用dp[x][y] 来表示到达(x,y)这个点的路径最短长度
dp[x][y]的状态变化,主要看dp[x-1][y] 和 dp[x][y-1](如果没越界的话)
所以可以先初始化dp[][]的左边 和 上边——因为dp[x][0] 只能dp[x-1][0] + grid[x][0]这样走
剩下的 位于矩阵右下角的元素 dp[x][y] = min(dp[x-1][y],dp[x][y-1]) + grid[x][y];
BFS数据量小的话枚举出来所有数据也可以做,数据量太大就没办法了(会超时) 这边不给代码了
C++代码
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {//倒退:dp[row-1][col-1] = min(dp[row-2][col-1],dp[row-1][col-2]);//分析状态:1. x = 0, y > 0 dp[x][y] = dp[x][y-1] + grid[x][y];// 2. x > 0, y = 0 dp[x][y] = dp[x-1][y] + grid[x][y];// 3. x > 0, y > 0 dp[x][y] = min(dp[x-1][y],dp[x][y-1]) + grid[x][y];int row = grid.size();int column = grid[0].size();vector<vector<int>>dp(row,vector<int>(column));dp[0][0] = grid[0][0];// 初始化两条边for(int x = 1 ; x < row ; ++x){dp[x][0] = dp[x-1][0] + grid[x][0];}for(int y = 1 ; y < column ; ++y){dp[0][y] = dp[0][y-1] + grid[0][y];}// 遍历右下角的矩阵for(int x = 1 ; x < row ; ++x)for(int y = 1 ; y < column ; ++y){dp[x][y] = min(dp[x-1][y] , dp[x][y-1]) + grid[x][y];}return dp[row - 1][column - 1];}
};
结算页面
这篇关于稀碎从零算法笔记Day51-LeetCode:最小路径和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!