剑指 Offer 47 礼物的最大价值

标签: 剑指 Offer 发布于:2022-02-26 23:25:55 编辑于:2022-02-26 23:31:12 浏览量:370

概述

https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

动态规划法

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/