小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
[编程题]年终奖
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
int m=board.length,n=board[0].length;
for(int i=1;i<m;i++){
board[i][0]+=board[i-1][0];
}
for(int j=1;j<n;j++){
board[0][j]+=board[0][j-1];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
board[i][j]+=Math.max(board[i-1][j],board[i][j-1]);
}
}
return board[m-1][n-1];
}
}
发表于 2023-09-08 17:38:52
回复(0)
//动态规划，不使用额外二维数组
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
//初始化
int rowPre = 0; int colPre = 0;
for (int i = 1; i<6; i++) {
board[0][i] += rowPre;
board[i][0] += colPre;
rowPre = board[0][i];
colPre = board[i][0];
}
// write code here
for (int i=1; i<6; i++) {
for (int j=1; j<6; j++) {
board[i][j] += Math.max(board[i-1][j],board[i][j-1]);
}
}
return board[5][5] + board[0][0];
}
}
发表于 2022-09-03 10:18:59
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
int row = board.length;
int col = board[0].length;
for(int i = 1;i < row;i++){
board[i][0] = board[i - 1][0] + board[i][0];
}
for(int j = 1;j < col;j++){
board[0][j] = board[0][j - 1] + board[0][j];
}
for(int i = 1;i < row;i++){
for(int j = 1;j < col;j++){
board[i][j] = Math.max(board[i - 1][j],board[i][j - 1])+board[i][j];
}
}
return board[row - 1][col - 1];
}
}
发表于 2022-04-26 15:54:35
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
if(board==null) return 0;
int[][] dp=new int[7][7];
//dp[1][1]=board[0][0];
for(int i=1;i<7;i++){
for(int j=1;j<7;j++){
dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])
+board[i-1][j-1];
}
}
return dp[6][6];
}
} dp问题,我的做法就是把dp数组左边界和上边界分别扩充一行和一列,因为我们要考虑i-1和j-1,这样处理就可以使得我们对6*6棋盘上任意格子处的状态都可以使用状态转移方程了,最后返回的就是dp数组最右下角的格子里的值就可以了.
发表于 2022-04-25 11:28:36
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
int[][] dp =new int[board.length][board[0].length];
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
if(i==0&&j==0){dp[0][0]=board[0][0];continue;}
if(i==0 && dp[i][j-1]!=0 && board[i][j]>100 && board[i][j]<1000){
dp[0][j]=dp[0][j-1]+board[0][j];continue;
}
if(j==0 && dp[i-1][j] !=0 && board[i][j]>100 && board[i][j]<1000){
dp[i][j]=dp[i-1][j]+board[i][j];continue;
}
if((dp[i-1][j]!=0 || dp[i][j-1]!=0) && board[i][j]>100 && board[i][j]<1000){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+board[i][j];continue;
}
}
}
return dp[dp.length-1][dp[0].length-1];
}
}
发表于 2022-01-13 23:52:49
回复(0)
//dfs
import java.util.*;
public class Bonus {
int value=0;
public int getMost(int[][] board) {
// write code here
dfs(board,0,0,0);
return value;
}
private void dfs(int[][] board, int sum, int i, int j){
if(i==5 && j==5){
value=Math.max(value,sum+board[i][j]);
return;
}
if(i>=6 || j>=6) return;
dfs(board,sum+board[i][j],i+1,j);
dfs(board,sum+board[i][j],i,j+1);
}
}
发表于 2021-07-20 10:47:10
回复(0)
//递归
public class Bonus {
public int getMost(int[][] board) {// write code here
return getNum(board, 5, 5);
}
public int getNum(int [][] res,int i,int j){
if (i == 0 && j == 0) {
return res[0][0];
}
if (i < 1) {
return getNum(res,i,j-1)+res[i][j];
}
if (j < 1) {
return getNum(res,i-1,j)+res[i][j];
}
return Math.max(getNum(res,i-1,j), getNum(res,i,j-1)) + res[i][j];
}
发表于 2021-04-10 13:05:46
回复(0)
import java.util.*;
public class Bonus {
int[] dir = {1,0,1};
int max_ = Integer.MIN_VALUE;
ArrayList<Integer> ret = new ArrayList<Integer>();
public void helpgetMost(int[][] board,int i,int j,int sum) {
if(i>=board.length || j>=board[0].length )
return;
if(i+j== board.length+board[0].length-2){
max_ = Math.max(max_,sum+board[i][j]);
return;
}
sum = sum+board[i][j];
for(int k=0;k<dir.length-1;k++){
helpgetMost(board,i+dir[k],j+dir[k+1],sum);
}
}
public int getMost(int[][] board) {
helpgetMost(board,0,0,0);
return max_;
}
public class Bonus {
int[] dir = {1,0,1};
int max_ = Integer.MIN_VALUE;
ArrayList<Integer> ret = new ArrayList<Integer>();
public void helpgetMost(int[][] board,int i,int j,int sum) {
if(i>=board.length || j>=board[0].length )
return;
if(i+j== board.length+board[0].length-2){
max_ = Math.max(max_,sum+board[i][j]);
return;
}
sum = sum+board[i][j];
for(int k=0;k<dir.length-1;k++){
helpgetMost(board,i+dir[k],j+dir[k+1],sum);
}
}
public int getMost(int[][] board) {
helpgetMost(board,0,0,0);
return max_;
}
}
深度遍历的思想。
发表于 2021-01-27 23:50:32
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
int n=board.length; // 行数
int m=board[0].length; // 列数
int[] dp=new int[m+1]; //加一列虚拟列
for (int i=0;i<n;i++){
for (int j=1;j<m+1;j++){ // 列从第二列开始
if(board[i][j-1]>100&&board[i][j-1]<1000){
dp[j]=Math.max(dp[j],dp[j-1])+board[i][j-1];
}
else{
dp[j]=0;
}
}
}
return dp[m];
}
} 我实在是没有想通为什么有人说不需要对大于100小于1000进行判断，可能是我的段位不够吧，这里我的题解是加上了对大于小于的判断，具体的做法是把不满足礼物价值的点的dp值设置为0（因为最后路径肯定不从这里过），不知道对不对，欢迎指正。
发表于 2020-03-12 21:22:51
回复(0)
思路：
除了第一行或者第一列外，矩阵其余每个点的上一步走法都来自该点上方或者左方，该点选择上方或左方两个点中累加和最大的点进行累加，矩阵右下角那个点的值就是最佳走法获得的最大价值，代码如下
public int getMost(int[][] board) {
for(int i=1;i<6;i++){
board[0][i]+=board[0][i-1];//先初始化第一行
board[i][0]+=board[i-1][0];//先初始化第一列
}
for(int i=1;i<6;i++){
for(int j=1;j<6;j++){//第二行第二列开始，从上到下从左到右进行最大累加
board[i][j]+= board[i-1][j]>board[i][j-1] ? board[i-1][j] : board[i][j-1];
}
}
return board[5][5];//最佳走法获得的最大价值
}
for(int i=1;i<6;i++){
board[0][i]+=board[0][i-1];//先初始化第一行
board[i][0]+=board[i-1][0];//先初始化第一列
}
for(int i=1;i<6;i++){
for(int j=1;j<6;j++){//第二行第二列开始，从上到下从左到右进行最大累加
board[i][j]+= board[i-1][j]>board[i][j-1] ? board[i-1][j] : board[i][j-1];
}
}
return board[5][5];//最佳走法获得的最大价值
}
发表于 2018-08-19 01:13:26
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
int[][] dp=new int[6][6];
//初始化数组
for(int i=0;i<6;i++){
for(int o=i;o<6;o++){
dp[i][5]+=board[o][5];
}
}
for(int i=0;i<6;i++){
for(int o=i;o<6;o++){
dp[5][i]+=board[5][o];
}
}
//递归状态方程
for(int i=4;i>=0;i--){
for(int j=4;j>=0;j--){
dp[i][j]=Math.max(dp[i+1][j]+board[i][j],dp[i][j+1]+board[i][j]);
}
}
return dp[0][0];
}
}
发表于 2018-01-27 11:55:59
回复(0)
// 状态转移方程：dp[x][y] = max(dp[x-1][y],dp[x][y-1]) + board[x][y];
import java.util.*;
public class Bonus {
int[][] dp = new int[6][6]; // 存放每个位置最大价值
public int getMost(int[][] board) {
return dp(board, 5, 5);
}
public int dp(int[][] board,int x,int y){
// 如果出界，返回0
if(x<0 || y<0)return 0;
if(dp[x][y]==0){ // 如果之前未保存过当前最大位置的价值，则求之
int p1 = dp(board, x-1, y);// 从左侧过来时的最大值
int p2 = dp(board, x, y-1);// 从上册过来时的最大值
dp[x][y] = (p1>p2?p1:p2)+board[x][y];// 取上、左侧中较大的加上此位置的礼物价值即得当前位置最大礼物价值
}
return dp[x][y]; // 返回当前位置礼物最大值
}
}
发表于 2017-05-19 15:21:28
回复(0)
//常规动态规划题，矩阵从左上角到右下角
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
int[][] dp = new int[6][6];
dp[0][0] = board[0][0];
for(int i=1;i<6;i++){
dp[0][i]=dp[0][i-1]+board[0][i];
}
for(int i=1;i<6;i++){
dp[i][0]=dp[i-1][0]+board[i][0];
}
for(int i=1;i<6;i++){
for(int j=1;j<6;j++){
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]) + board[i][j];
}
}
return dp[5][5];
}
}
发表于 2017-03-04 18:32:07
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
if(board == null || board.length==0){
return 0;
}
for(int i=0;i<board.length;i++){
for (int j = 0; j < board[0].length; j++) {
if(i==0 && j==0){
// 奖金就是第一个格子本身
}else if(i==0){
// 说明在第一行 第一行的奖金只能来自第一行左边的格子
// 奖金等于当前格子的奖金加上左边格子的奖金
board[0][j] += board[0][j-1];
}else if(j==0){
// 说明在第一列 第一列的奖金只能来自列的上面个格子
// 奖金等于当前格子的奖金加上上面格子的奖金
board[i][0] += board[i-1][0];
}else {
// 来自上面或者左边的格子，选取最大奖金的。
// 最大奖金等于当前格子奖金加上左边或上面格子中奖金数大的那个
board[i][j] +=Math.max(board[i][j-1],board[i-1][j]);
}
}
}
// 增加通用型，直接用数据的长度吧
return board[board.length-1][board[0].length-1];
}
}
编辑于 2016-09-03 23:27:13
回复(2)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
for (int i = 1; i < board.length; i ++ ) {
board[i][0] += board[i - 1][0];
}
for (int i = 1; i < board[0].length; i ++ ) {
board[0][i] += board[0][i - 1];
}
for (int i = 1; i < board.length; i ++ ) {
for (int j = 1; j < board[0].length; j ++ ) {
board[i][j] += Math.max(board[i - 1][j], board[i][j - 1]);
}
}
return board[board.length - 1][board[0].length - 1];
}
}
发表于 2016-08-31 19:07:19
回复(0)
import java.util.*;
public class Bonus {
public int getMost(int[][] board) {
// write code here
int[][] dp = new int[6][6];
for (int i = 0; i < board.length; ++i) {
for (int j = 0; j < board[i].length; ++j) {
int tmp = board[i][j];
if (i > 0 && j > 0) {
dp[i][j] = Math.max(dp[i - 1][j] + tmp, dp[i][j - 1] + tmp);
} else if (i == 0 && j == 0) {
dp[i][j] = tmp;
} else if (i == 0) {
dp[i][j] = dp[i][j - 1] + tmp;
} else {
dp[i][j] = dp[i - 1][j] + tmp;
}
}
}
return dp[5][5];
}
}
发表于 2016-08-29 09:49:58
回复(1)
问题信息
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
