首页 > 试题广场 >

年终奖

[编程题]年终奖

热度指数：28044 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。

给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。

算法知识视频讲解

Python

acechen15

class Bonus:
    def getMost(self, board):
        # write code here
        if not board&nbs***bsp;len(board) == 0&nbs***bsp;len(board[0]) == 0:
            return 0
        rows = len(board)
        cols = len(board[0])
        dp = [[0] * cols for _ in range(rows)]
        dp[0][0] = board[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i - 1][0] + board[i][0]
        for j in range(1, cols):
            dp[0][j] = dp[0][j - 1] + board[0][j]
        for row in range(1, rows):
            for col in range(1, cols):
                dp[row][col] = max(dp[row - 1][col], dp[row][col - 1]) + board[row][col]
        return dp[-1][-1]

发表于 2021-08-22 16:04:53 回复(0)

Python

牛客706616761号

class Bonus:
def getMost(self, board):
# write code here
n=len(board)
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+board[i-1][j-1];
return dp[-1][-1]

编辑于 2020-08-06 15:51:22 回复(0)

Python

牛客598283358号

board[i][j]记录着当前为止的最大值,先将第一列和第一行的走过最大值记录下来,然后从board[1][1]开始到board[m][n]每一格为止的最大值为上面和左边两个中的最大值加本身,用的是动态规划的思路

class Bonus:
    def getMost(self, board):
        # write code here
        m = len(board[0])
        n = len(board)
        for i in range(1,m):
            board[0][i] += board[0][i-1]
        for j in range(1, n):
            board[j][0] += board[j-1][0]
        for i in range(1, m):
            for j in range(1, n):
                board[j][i] += max(board[j-1][i],board[j][i-1])
        return board[n-1][m-1]

发表于 2020-05-13 23:36:59 回复(0)

Python

lx的流星

# -*- coding:utf-8 -*-

class Bonus:
    def getMost(self,board):
        # write code here
        dp=[]
        for i in range(6):
            dp.append([0]*6)
        dp[0][0]=board[0][0]
        for i in range(1,6):
            dp[0][i]=dp[0][i-1]+board[0][i]
        for i in range(1,6):
            dp[i][0]=dp[i-1][0]+board[i][0]
        for i in range(1,6):
            for j in range(1,6):
                dp[i][j]=max(dp[i-1][j]+board[i][j],dp[i][j-1]+board[i][j])
        return dp[-1][-1]

发表于 2019-07-18 10:49:49 回复(0)

Python

广安亭主

class Bonus:
def getMost(self, board):
row,col = len(board),len(board[0])
dp = [[0 for _ in range(col+1)] for _ in range(row+1)]
for i in range(1,row+1):
for j in range(1,col+1):
dp[i][j] = max(dp[i-1][j]+board[i-1][j-1],dp[i][j-1]+board[i-1][j-1])
return dp[row][col]

发表于 2019-05-13 20:47:07 回复(0)

Python

TimeMac

class Bonus:
    def getMost(self, board): #递归实现
        maxValue = [0]        #python2没有nonlocal关键词，就使用可变的对象list
        def pathCross(nowValue,i,j):
            if i == j == 5:
                maxValue[0] = max(nowValue+board[i][j],maxValue[0])
            else:
                if i+1 < 6:
                    pathCross(nowValue+board[i][j],i+1,j)
                if j+1 < 6:
                    pathCross(nowValue+board[i][j],i,j+1)
        pathCross(0,0,0)
        return maxValue[0]

编辑于 2018-10-19 21:30:14 回复(0)

Python

anai

class Bonus:
    def getMost(self, board):
        # write code here
        n=len(board)
        dp=[[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(n):
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+board[i][j]
        return dp[n-1][n-1]

发表于 2018-05-09 10:00:43 回复(0)

Python

goeatit

动态规划。
求解每一步的最优，该步的最有取决于该位置上面或左边的值。先计算第一行和第一列，
第一行每步只能向右，第一列每步只能向下。
创建一个新的6*6矩阵存储到达该步的最优解。
class Bonus:
    def getMost(self, board):
        got = [[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
        got[0][0] = board[0][0]
        for i in range(1,6):                    #calculate the 1st row
            got[0][i] = got[0][i-1] + board[0][i]
        for i in range(1 ,6):                   #calculate the 1st column
            got[i][0] = got[i-1][0] + board[i][0]
        for i in range(1,6):
            for j in range(1,6):
                if got[i][j-1] > got[i-1][j]:
                    got[i][j] = board[i][j] + got[i][j-1]
                else:
                    got[i][j] = board[i][j] + got[i-1][j]
        return got[5][5]

发表于 2017-07-27 23:03:03 回复(0)

Python

izayacode

二维表的动态规划 + 设置虚拟边界

class Bonus:
    def getMost(self, board):
        l = [[0 for i in range(7)] for j in range(7)]
        for i in range(1,7):
            for j in range(1,7):
                l[i][j] = board[i-1][j-1] + max(l[i-1][j], l[i][j-1])
        return l[6][6]

编辑于 2016-08-12 07:56:48 回复(0)