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

╰半夏微凉° 2022-09-09 15:00 169阅读 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 条评论，169人围观）

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

相关阅读

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

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

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

相关剑指offer面试题47(java版):礼物的最大价值

[welcome to my blog][] 剑指offer面试题47(java版):礼物的最大价值题目描述在一个 mn 的棋盘的每一格都放有一个

快来打我*/ 2023年07月07日 11:25/ 0 赞/ 2 阅读

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

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

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

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

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

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

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

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

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

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

剑指 Offer 47. 礼物的最大价值题目难度：中等方法一：动态规划 > 链接：[https://leetcode-cn.com/problems/l

忘是亡心i/ 2022年10月16日 04:44/ 0 赞/ 4 阅读

相关力扣-剑指 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 赞/ 170 阅读

相关力扣-剑指 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 赞/ 128 阅读

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

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

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

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

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

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