64. 最小路径和(Leetcode)

文章目录

前言
一、题目分析
二、算法原理
- 1.状态表示
- 2.状态转移方程
- 3.初始化
- 4.填表顺序
- 5.返回值是什么
三、代码实现
总结

前言

在本文章中，我们将要详细介绍一下Leetcode6最小路径相关的内容

一、题目分析

在这里插入图片描述

二、算法原理

1.状态表示

列出dp表，dp[i][j]代表到达该位置数字之和最小

2.状态转移方程

根据最近一步，划分问题
1.dp[i][j]从上面位置再往下走一步，到达该位置，这个上边位置就是dp[i-1][j]
2.dp[i][j]从左面位置再往右走一步，到达该位置，这个上边位置就是dp[i][j-1]
3.二者最小值再加上当前位置的值就是dp[i][j]

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+gr[i][j];

3.初始化

a.下标的映射关系
b.虚拟位置的值，保证后面填表正确
c.注意开头位置的初始化，不要越界
在这里插入图片描述
dp[0][1]和dp[1][0]位置要初始化为0；
其余虚拟位置初始化为INT_MAX;
（注意图中的三个位置）

4.填表顺序

从上到下，从左到右

5.返回值是什么

dp[m][n]

三、代码实现

class Solution {
public:
    int minPathSum(vector<vector<int>>& gr) 
    {
        //建表
        int m=gr.size();
        int n=gr[0].size();
        int dp[m+1][n+1];

        //初始化
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=n;j++)
            {
                dp[i][j]=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])+gr[i-1][j-1];
            }
        }
        //返回值
        return dp[m][n];
    }
};