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

矩阵的最小路径和

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

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

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

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