题解 | #矩阵的最小路径和#

矩阵的最小路径和

https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb

#include <vector>
class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> dp(n + 1, 25000000);
        for (int i = 1; i <= m; ++i) {
            if (i == 1) {
                dp[0] = 0;
            } else {
                dp[0] = 25000000;
            }
            for (int j = 1; j <= n; ++j) {
                dp[j] = min(dp[j], dp[j - 1]) + matrix[i - 1][j - 1];
            }
        }
        return dp[n];
    }
};

思路:常规动态规划。dp[i][j]表示走到(i, j)的最小路径和,只可能从(i - 1, j)或(i, j - 1)走来。

全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 12:10
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务