动态规划-64.最小路径和-力扣(LetCode)

白天的黑夜

发布于 2025-10-22 16:54:21

890

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

一、题目解析

从左上角到右下角使得数字总和最小且只能向下或向右移动

二、算法原理

1.状态表示

我们需要求到达[i,j]位置时数字总和的最小值，所以dp[i][j]表示：到达[i,j]位置时，路径数字总和的最小值。

2.状态转移方程

到达[i,j]之前要先到达[i-1,j]或[i,j-1]位置，比较得出最小值然后加上grid[i][j]的值

3.初始化

4.填表顺序

从左往右，从上到下

5.返回值

返回dp[m][n]

建议自己上手实现一下，链接：64. 最小路径和 - 力扣（LeetCode）

三、代码示例

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(),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];
    }
};