LeetCode刷题--- 最小路径和

个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

?http://t.csdnimg.cn/yUl2I

【C++】? ??

??????http://t.csdnimg.cn/6AbpV

数据结构与算法

????http://t.csdnimg.cn/hKh2l

前言：这个专栏主要讲述动态规划算法，所以下面题目主要也是这些算法做的 ?

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

最小路径和

题目链接：最小路径和

题目

给定一个包含非负整数的?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

解法

题目解析

• 给定一个包含非负整数的?m?x?n?网格?grid?。
• 找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
• 每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

算法原理讲解

我们这题使用动态规划，我们做这类题目可以分为以下五个步骤

1. 状态显示
2. 状态转移方程
3. 初始化（防止填表时不越界）
4. 填表顺序
5. 返回值

• 状态显示

• 状态转移方程

如果dp[i][j] 表?到达 到达 [i, j] 位置处的最?路径和，那么到达 [i, j] 位置之前的??步，有两种情况：

• 从 [i - 1, j] 向下??步，转移到 [i, j] 位置；
• 从 [i, j - 1] 向右??步，转移到 [i, j] 位置。

• 初始化（防止填表时不越界）

• 辅助结点??的值要「保证后续填表是正确的」；
• 「下标的映射关系」。

• 填表顺序

• 返回值

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));

        dp[0][1] = dp[1][0] = 0;            // 初始化

        // 填表
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];
            }
        }

        return dp[m][n];
    }
};