Leetcode题解剑指 Offer 47. 礼物的最大价值

PROBLEM

难度中等

MY ANSWER

典型的动态规划，不能使用贪心时，就看能否使用动态规划。转移方程为：

时间复杂度O(mn)，空间复杂度O(mn)。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.empty()) {
            return 0;
        }
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0));
        dp[0][0] = grid[0][0];
        for(int i = 1; i < dp[0].size(); i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int i = 1; i < dp.size(); i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i = 1; i < dp.size(); i++) {
            for(int j = 1; j < dp[0].size(); j++) {
                dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[dp.size()-1][dp[0].size()-1];
    }
};

BETTER SOLUTION

若可以在原矩阵上修改，就可以将空间复杂度降低到常数。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        if(grid.empty()) {
            return 0;
        }
        for(int i = 1; i < grid[0].size(); i++) {
            grid[0][i] += grid[0][i-1];
        }
        for(int i = 1; i < grid.size(); i++) {
            grid[i][0] += grid[i-1][0];
        }
        for(int i = 1; i < grid.size(); i++) {
            for(int j = 1; j < grid[0].size(); j++) {
                grid[i][j] += max(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[grid.size()-1][grid[0].size()-1];
    }
};

SUMMARY

二维vector初始化一个和grid一样大的矩阵dp：vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0));
若允许原地修改，可考虑通过原地修改降低空间复杂度。