力扣-剑指 Offer 47.礼物的最大价值（C++）- 动态dp

╰半夏微凉° 2022-09-09 15:00 158阅读 0赞

题目链接：[https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/][https_leetcode-cn.com_problems_li-wu-de-zui-da-jie-zhi-lcof]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
    public:
        int maxValue(vector<vector<int>>& grid) {
        
            //动态规划要考虑的三点：状态怎么表示，状态怎么计算，考虑边界情况
            //1、状态：f[i,j]
            //2、状态计算：f[i,j]=max(f[i-1,j],f[i,j-1])+gift[i,j];
            //3、边界：f[i,0]=f[0,j]=0     待求：f[n,m]
    
            int row=grid.size(),col=grid[0].size();
            vector<vector<int>> f(row+1,vector<int>(col+1));
    
            for(int i=1;i<=row;i++)
                for(int j=1;j<=col;j++)
                f[i][j]=max(f[i-1][j],f[i][j-1])+grid[i-1][j-1];//注：如果从0开始，不方便-1
    
            return f[row][col];
        }
    };

[https_leetcode-cn.com_problems_li-wu-de-zui-da-jie-zhi-lcof]: https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/695d50c1666c468891bcb2252e0eb766.png

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划之剑指 Offer 47. 礼物的最大价值

1. 题目分析题目链接选自力扣 : [剑指 Offer 47. 礼物的最大价值][Offer 47.] ![image.png][] 这个题, 如果抛开礼物价值不

一时失言乱红尘/ 2024年03月16日 22:37/ 0 赞/ 75 阅读

相关 [剑指offer]面试题第[47]题[JAVA][礼物的最大价值][动态规划]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

缺乏、安全感/ 2023年02月28日 11:22/ 0 赞/ 1 阅读

相关剑指Offer系列（java版，详细解析）47.礼物的最大价值

题目描述在一个 m\n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到

青旅半醒/ 2023年01月13日 09:35/ 0 赞/ 177 阅读

相关 LeetCode:剑指 Offer 47.礼物的最大价值(C语言)

题目描述：在一个 m\n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到

一时失言乱红尘/ 2022年12月16日 06:55/ 0 赞/ 139 阅读

相关【剑指Offer】47. 礼物的最大价值

[力扣][Link 1] 题目描述在一个 m\n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次

墨蓝/ 2022年12月01日 14:05/ 0 赞/ 127 阅读

相关剑指 Offer 47. 礼物的最大价值

题目在一个 m\n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋

野性酷女/ 2022年11月21日 14:49/ 0 赞/ 154 阅读

相关力扣-剑指 Offer 47.礼物的最大价值（C++）- 动态dp

题目链接：[https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/][https_leetcode-cn.

╰半夏微凉°/ 2022年09月09日 15:00/ 0 赞/ 159 阅读

相关力扣-剑指 Offer 63. 股票的最大利润（C++）-动态dp

题目链接：[https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/][https_leetcode-cn

旧城等待，/ 2022年09月09日 12:52/ 0 赞/ 123 阅读

相关剑指Offer47:礼物的最大价值

在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格直到到达棋盘的右下角。给定一个

港控/mmm°/ 2022年01月31日 23:04/ 0 赞/ 212 阅读

相关【剑指offer】47 礼物的最大价值

[面试题47. 礼物的最大价值][47.] 难度中等30 在一个 m\n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格

￡神魔★判官ぃ/ 2021年10月03日 02:26/ 0 赞/ 277 阅读