首页 > 试题广场 >

年终奖

[编程题]年终奖

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

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

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

算法知识视频讲解

Java

小谷围做题家

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)

Java

two倩

public int getMost(int[][] board) {

int[][] dp = new int[7][7];
dp[0][0] = 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 - 1][j - 1];
}
}
return dp[6][6];
}

发表于 2022-09-08 22:19:33 回复(0)

Java

牛客88108452号

//动态规划，不使用额外二维数组

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)

Java

来学习的小张

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)

Java

哥们给个offer

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)

Java

天边的魔术师

import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        
        int[][] dp = new int[7][7];
        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];
    }
}

和机器人走路一样

发表于 2022-03-17 18:55:41 回复(0)

Java

wanbf

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)

Java

SnailLLL

//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)

Java

罗天天

//递归

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)

Java

KxxxxxK

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_;
}

}

深度遍历的思想。

发表于 2021-01-27 23:50:32 回复(0)

Java

xxm417

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)

Java

放学后我不走~

思路：

除了第一行或者第一列外，矩阵其余每个点的上一步走法都来自该点上方或者左方，该点选择上方或左方两个点中累加和最大的点进行累加，矩阵右下角那个点的值就是最佳走法获得的最大价值，代码如下

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];//最佳走法获得的最大价值
}

发表于 2018-08-19 01:13:26 回复(0)

Java

安徒生的谎言

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)

Java

Eleven23

// 状态转移方程：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)

Java

王小叶

//常规动态规划题，矩阵从左上角到右下角
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)

Java

追赶大废

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)

Java

詆調壹點

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)

Java

JustYoung

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)