剑指offer47 礼物的最大价值【DP】
题目描述
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
1 | 输入: |
提示:
0 < grid.length <= 200
0 < grid[0].length <= 200
解题思路
方法一:动态规划
利用动态规划的思想,使得到达每个点的价值都为最大值。
状态转移方程: 选择来自 上方 或者 左边 最大价值的。
$$
dp[i][j]=dp[i][j]+Math.max(dp[i-1][j],dp[i][j-1])
$$
代码实现
1 | class Solution { |
复杂度分析
时间复杂度:O($n^2$)
空间复杂度:O(1)
资料
剑指offer47 礼物的最大价值【DP】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.