小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
[编程题]年终奖
题目 牛客 解题思路 这道题属于贪心算法，但本质仍然是动态规划。对于这样一个棋盘，到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到，要么是前一列(i,j-1)向右移动一列得到因此我们可以建立一个相同的矩阵gifts,gifts[i][j]表示从起点到i,j这一点中某条路径代表的礼物
展开全文
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
int row = board.length;
int col = board[0].length;
int[][] bonus = new in
展开全文
思路 递归dp回溯dp[i][j]+max(getMost(i-1,j),getMost(i,j-1)),状态转移方程 代码 import java.util.*;
public class Bonus {
public int getMost(int[][] board,int i,int
展开全文
【剑指offer】礼物的最大价值（python） 使用动态规划求解，DFS过于复杂，不是最优解。每次都求到达相邻的两个列中的最大值。 # -*- coding:utf-8 -*-
class Bonus:
def getMost(self, board):
# write
展开全文
class Bonus {
public:
int getMost(vector<vector<int> > board) {
// write code here
return getMost(board, 0, 0, 0);
展开全文
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
//动态规划
int row = board.length;
int col = boa
展开全文
class Bonus {
public:
int getMost(vector<vector<int> > board) {
int row =board.size();
int col =board[0].size();
展开全文
import java.util.*;
public class Bonus {
public static int getMost(int[][] board) {
int row=board.length;
int col=board[0].length
展开全文
定义表示走到i行j列时能获得的最高奖金，由于只能向右走或者向下走，要求最高奖金，那么可得转移方程：即当前能获得的最大奖金为 左边和上边一格中的较大值+当前格子的值
#include <vector>
class Bonus {
public:
int getMost(vec
展开全文
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
int row = board.length;
i
展开全文
问题信息
通过挑战的用户
查看代码-
2023-03-10 09:50:27
-
2023-03-09 12:42:33 -
2023-03-08 15:18:12 -
2023-03-07 00:09:44
-
2023-03-06 20:57:38
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
