面试题47. 礼物的最大价值

原创
2020/04/17 04:46
阅读数 29

面试题47. 礼物的最大价值



image.png

面试题47.礼物的最大价值

七分享

28

文切换为英文关注回反馈

难度中等

收藏

在一个m的机盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0),你可以从模的左上角开

始卓格子里的礼物,并每次向右或者向下移动一格,直到到达模盘的右下.给定一个棋盘及其上面的礼物的价

值,请计算你最多能拿到多少价值的礼物?

示例1:

输入:

[1,3

[1,5,

[4,2,

输出:12

解释:路径1-3-5-2-1可以拿到最多价值的礼物

提示:

0<grid.length<200

0<gridroj.1ength

200

9.593

通过次数

提交次数14.284

动态规划

  1. 找到动态规划多项式
  2. 找到边界情况, 第一行, 第一列
  3. 初始化动态规划的数组
  4. 返回最后一个元素
package main

func maxValue(grid [][]int) int {
    row :=len(grid)// 行
    column := len(grid[0])//列
    dp := make([][]int,row)
    for i:=range dp{
        dp[i] = make([]int,column)
    }
    dp[0][0]= grid[0][0]
    for i :=1;i<row;i++{//第一列行
        dp[i][0]= dp[i-1][0]+grid[i][0]
    }
    for j:=1;j<column;j++{//第一行的列
        dp[0][j] = dp[0][j-1]+grid[0][j]
    }
    for i:=1;i<row;i++{
        for j:=1;j<column;j++{
            dp[i][j]= grid[i][j]+Max(dp[i][j-1],dp[i-1][j])
        }
    }
    return dp[row-1][column-1]
}
func Max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

//面试题47. 礼物的最大价值
func main() {
    
}

image.png

通过

执行结果:

显示详情>

执行用时:8ms,在所有GO提交中击败了94.81%的用户

00%的用户

内存消耗:4.4MB,在所有GO提交中击败了100.00%

炫耀一下:

写题解,分享我的解题思路

进行下一个挑战:

地下城游戏

困难

青娃过河

困难

连续差相同的数字

中等

本文同步分享在 博客“羊羽”(other)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享

作者的其它热门文章

加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部