【LeetCode】 礼物的最大价值 Java 题解
题目描述
在一个 m * n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
复制代码
思路分析
这个题目是经典的动态规划题目,我们需要认真分析。有的同学可能不知道什么是动态规划,动态规划的概念是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
分析题目,明确每次移动步骤是 向右或者向下移动一格,需要求得多做的价值礼物。也就是向右或者向下的最大值,加上当前的礼物的价值,最终到达右下角即为最大。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(m * n), 空间复杂度是 O(1)
二维数组是考察动态规划的常见题目,我们一般是要明确针对整个数组建立 dp 数组,首先需要对第 0 行和第 0 列进行初始化。然后根据题意,分析动态转移方程,得到最终结果。
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/35752f00a7a300db6fee8b3d4】。文章转载请联系作者。
评论