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

矩阵的最小路径和

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

动态规划的独孤九剑,建议兄弟们去学习一下,还是比较受用的。
这个题用动态规划非常自然,定义状态dp[i][j]为走到位置(i,j)的最小路径和。
其他的就顺其自然了。

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return 0;
        }
        
        int m=matrix.size();
        int n=matrix[0].size();
        int dp[m][n];
        dp[0][0] = matrix[0][0];
        
        for(int i=1;i<m;i++){
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }
        
        for(int i=1;i<n;i++){
            dp[0][i] = dp[0][i-1] + matrix[0][i];
        }
        
        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]) + matrix[i][j];
            }
        }
        
        return dp[m-1][n-1];
    }
};


全部评论

相关推荐

05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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