陈中正的网络日志

LeetCode: Minimum Path Sum

题目

https://oj.leetcode.com/problems/minimum-path-sum/

分析

动态规划题,

某一点的MinimumPathSum = min(左侧点的MinimumPathSum, 上侧点的MinimumPathSum) + 该点的数值

不过第一行和第一列的MinimumPathSum有些特殊,需要单独处理一下。

代码

class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> res(grid);

        //First row and first col 's Minimum Path Sum
        for (int i = 1; i < m; i++)
            res[i][0] += res[i-1][0];
        for (int i = 1; i < n; i++)
            res[0][i] += res[0][i-1];

        //Other points's Minimum Path Sum
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                res[i][j] += min(res[i-1][j], res[i][j-1]);

        return res[m-1][n-1];
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40868907

Categories:  OJ题解 

« LeetCode: Edit Distance LeetCode: Unique Paths II »