即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

LeetCode 64. Minimum Path Sum

编程语言 chenshx_sysu 14℃ 0评论

【题目】

Given a m x n grid
filled with non-negative numbers, find a path from top left to bottom right which 
minimizes the
sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

【题解】

这是一道典型的动态规划题目,令sum[i][j]为走到第i行第j列的格子时沿路上所有数字和最小的值,其动态转移方程为sum[i][j]=min(sum[i-1][j], sum[i][j-1])+grid[i][j],其中grid[i][j]为第i行第j列的格子上的数字,最后返回的结果为sum[m-1][n-1],m为行数,n为列数

【代码】

    int minPathSum(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size(); 
        vector> sum(m, vector(n, grid[0][0]));
        for (int i = 1; i < m; i++)
            sum[i][0] = sum[i - 1][0] + grid[i][0];
        for (int j = 1; j < n; j++)
            sum[0][j] = sum[0][j - 1] + grid[0][j];
            
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                sum[i][j]  = min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
                
        return sum[m - 1][n - 1];        
    }





转载请注明:CodingBlog » LeetCode 64. Minimum Path Sum

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情