礼物的最大价值
礼物的最大价值
问题陈述
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例:
1 | 输入: |
思路分析
可使用动态规划解决此题。
状态定义:设动态规划矩阵dp,dp[i,j]代表从棋盘的左上角开始,到达[i,j]单元格能拿到最多礼物的累积值。
转移方程:
-
当i=0,j=0时,为起始元素。
-
当i=0,j$\ne$0时,为矩阵第一行元素,只可能从左边到达。
-
当i$\ne$0,j=0时,为矩阵第一列元素,只可能从上边到达。
-
当,时,可从左边或上边到达,据题意取两者中的最大值
初始状态:dp[0][0]=grid[0][0]。
返回值:dp[m-1][n-1],其中m,n为矩阵的长宽,即返回dp右下角元素。
代码实现
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 淋竹调!
评论