首页 > 试题广场 >

年终奖

[编程题]年终奖

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

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

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

算法知识视频讲解

会呼吸旳痛

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int dp[6][6];
        dp[0][0]=board[0][0];
        
        for(int i=0;i<6;i++)
            for(int j=0;j<6;j++)
            {
            if(!j && !i)
                continue;
            else
                dp[i][j] = max((j==0)?0:dp[i][j-1],(i==0)?0:dp[i-1][j])+ board[i][j];
            
        }
        return dp[5][5];
    }
};

发表于 2016-08-18 00:41:48 回复(1)

一只补习的Fyu


	class Bonus {



	public:



	    int getMost(vector<vector<int> > board) {



	        if(board.empty()) return 0;



	        



	        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] += max(board[i - 1][j], board[i][j - 1]);



	            }



	        }



	    return board[5][5];



	    }



	};

发表于 2016-04-05 23:58:52 回复(0)

BlackMagician

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int m = board.size(), n = board[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] =
                    max(dp[i - 1][j], dp[i][j - 1]) + board[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

发表于 2018-05-29 14:03:04 回复(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)

忧郁的小菜鸟

import java.util.*;
//这道题用递归更简单写

public class Bonus {
    public int getMost(int[][] board) {
        // write code here
        return getM(board,0,0);
    }
    public int getM(int[][] board,int a,int b){
        if(a==5&&b==5)
            return board[5][5];
        else if(a==5&&b<5){
            return board[5][b]+getM(board,5,b+1);
        }
        else if(b==5&&a<5)
            return board[a][5]+getM(board,a+1,b);
        else{
            int c=getM(board,a+1,b);
            int d=getM(board,a,b+1);
            return board[a][b]+(c>=d?c:d);
        }
    }
}

发表于 2017-04-05 10:49:17 回复(0)

CiaoLiang

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
		int row = board.size();
        int col = board[0].size();
        vector<vector<int>> Dp(row,vector<int>(col,0));
        Dp[0][0]=board[0][0];
        for(int i=1; i<row; ++i){
            Dp[i][0] = Dp[i-1][0] + board[i][0];
        }
         for(int i=1; i<col; ++i){
            Dp[0][i] = Dp[0][i-1] + board[0][i];
        }
        for(int i=1; i<row; ++i){
            for(int j=1; j<col; ++j){
                Dp[i][j]=max(Dp[i-1][j],Dp[i][j-1])+board[i][j];
            }
        }
        return Dp[row-1][col-1];
    }
};

发表于 2016-09-04 22:23:37 回复(0)

今日看点

从后往前推

直白的说就是每次都求到达相邻的两个中的最大值；


	importjava.util.*;



	 



	publicclassBonus {



	    publicintgetMost(int[][] board) {



	        // write code here



	        intresult = 0;



	        result = getMost(board.length-1,board[board.length-1].length-1,board);



	        returnresult;      



	    }



	    publicintgetMost(inti,intj,int[][] board){



	        intresult = board[i][j];



	        intleft = 0;



	        inttop = 0;



	        if(i>0){



	            left = getMost(i-1,j,board);



	        }



	        if(j>0){



	            top = getMost(i,j-1,board);



	        }



	        if(left >=top){



	            result = result + left;



	        }else{



	            result = result + top;



	        }



	        returnresult;



	    }

}

发表于 2016-09-02 23:05:29 回复(0)

aweffr

// 我给一个递归版本的解答。思路就是对于任意点(i,j)，
// 它能取到的最大值取决于于(i-1,j)和(i,j-1)中的最大值。

public class Main {
	public static void main(String[] args) {
		int[][] testCase = new int[6][6];
		for(int i = 0; i < 6; i++) 
		{
			for (int j=0; j<6; j++)
			{
				testCase[i][j] = i + j + 1;
			}
		}
		System.out.println(getMost(testCase));
	}
	
	public static int getMost(int[][] board) {
		return getMost(board, 5, 5);
	}
	
	public static int getMost(int[][] board, int i, int j) {
		int max;
		if (i > 0 && j > 0)
		{
			max = board[i][j] + Math.max(getMost(board, i, j-1), getMost(board, i-1, j));
		}
		else if (i > 0 && j == 0)
		{
			max = board[i][j] + getMost(board, i-1, j);
		}
		else if (i == 0 && j > 0)
		{
			max = board[i][j] + getMost(board, i, j-1);
		}
		else
		{
			max = board[i][j];
		}
		return max;
	}
}

发表于 2016-09-01 14:30:20 回复(0)

雪焱

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int a[6][6];
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                a[i][j]=0;
            }
        }
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                if(i==0 && j==0){a[i][j]=board[0][0];}
                else if(i==0){a[i][j]=board[i][j]+a[i][j-1];}
                else if(j==0){a[i][j]=board[i][j]+a[i-1][j];}
                else
                    a[i][j]=board[i][j]+((a[i-1][j])>a[i][j-1]?a[i-1][j]:a[i][j-1]);
            }
        }
        return a[5][5];
    }

    }
;

因为只能向右或者向下所以一行一行计算就可以得到答案

编辑于 2021-04-07 10:33:48 回复(0)

负重前行。

动态规划解法：dp = Math.max(values[i - 1][j], values[i][j - 1]) + values[i][j].

 static int getMost(int[][] values){
        if (values == null || values.length == 0 || values[0].length == 0){
            return 0;
        }
        // 创建一个dp备忘录
        int m = values.length;
        int n = values[0].length;
        int[][] dp = new int[m][n];
        //初始化备忘录
        dp[0][0] = values[0][0];
        for (int i = 1; i < m; i++) dp[0][i] = values[0][i] + dp[0][i - 1];
        for (int i = 1; i < n; i++) dp[i][0] = values[i][0] + dp[i - 1][0];

        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + values[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

发表于 2020-12-08 10:40:27 回复(0)

枸杞很好

mport java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        // write code here
        if(board == null || board.length == 0 || board[0].length == 0)
            return 0;
        else{
            int n = board[0].length;
            int dp[] = new int[n];
            for(int[] values: board){
                dp[0] += values[0];
                for(int i=1;i<n;i++){
                    dp[i] = Math.max(dp[i-1],dp[i]) + values[i];
                }
            }
            return dp[n-1];
        }
    }
}

发表于 2020-09-09 17:38:31 回复(0)

C/C++

WZ_Dale

本题需要使用动态规划求解。

定义f(i,j)表示从左上角走到坐标(i，j)处能获得的最大奖励。

搜索所有从左上角走到右下角的路径，找到最优路径。

f(i,j)分三种情况：

第一列：f(i, 0) = f(i-1, 0) + board(i, 0)

第一行：f(0,j) = f(0, j - 1) + b(0, j)

其它位置：f(i, j) = max{f(i-1, j), f(i, j - 1)} + board(i, j)

最后返回右下角的值。

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<int>> vv(m, vector<int>(n, 0));
        vv[0][0] = board[0][0];
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                //如果是起点坐标，不做任何处理。
                if(i == 0 && j == 0){
                    continue;
                }
                //如果走在行的临界边，也就是第一行，那么他只能向右走
                //向右走的时候该点就要将后面的值加起来。
                else if(i == 0){
                    vv[i][j] = vv[i][j - 1] + board[i][j];
                }
                //如果走在列的临界边，也就是第一列，那么他只能向下走
                //向下走的时候该点就要将上面的值加起来。
                else if(j == 0){
                    vv[i][j] = vv[i - 1][j] + board[i][j];
                }
                //除去两个临界边，剩下的就是既能向右走，也能向下走，
                //这时候就要考虑走到当前点的所有可能得情况，也就是走到当前点
                //各自路径的和是不是这些所有到达该点路径当中最大的了。
                else{
                    vv[i][j] = max(vv[i - 1][j], vv[i][j - 1]) + board[i][j];
                }
            }
        }
        return vv[m - 1][n - 1];
    }
};

发表于 2020-06-26 15:19:46 回复(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)

✭

# -*- coding:utf-8 -*-
 
class Bonus:
    def getMost(self, board):
        # write code here
        dp = [[0 for j in range(6)] for i in range(6)]#初始化dp矩阵
        dp[0][0] = board[0][0]
        for i in range(5):
            dp[0][i+1] = dp[0][i]+board[0][i+1]#第一行的最大值，只能是从dp[0][0]一直向右走
            dp[i+1][0] = dp[i][0]+board[i+1][0]#第一列的最大值，只能是从dp[0][0]一直向下走
        for j in range(1,6):
            for k in range(1,6):
                #当前位置的最大值，只能由上一次位置向下或向右所得
                #故当前位置最大值等于max(上面， 左边)+当前位置的礼物值
                dp[j][k] = max(dp[j-1][k], dp[j][k-1])+board[j][k]
        return dp[5][5]

发表于 2019-08-29 16:44:06 回复(0)

C/C++

全论坛最菜

一维dp，参考矩阵中的最大路径和（C++）

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int m = board.size();
        int n = board[0].size();
        vector<int > dp(n, 0);
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i == 0 && j == 0){
                    dp[j] = board[0][0];
                }if(i == 0){
                    dp[j] = dp[j-1] + board[0][j];
                }else if(j == 0){
                    dp[j] += board[i][0];
                }else{
                    dp[j] = max(dp[j], dp[j-1]) + board[i][j];
                }
            }
        }
        return dp[n-1];
    }
};

发表于 2019-04-09 21:07:10 回复(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)

kestars

import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        int n=board.length;
        int m=board[0].length;
        int[][] dp=new int[board.length][board[0].length];
        dp[0][0]=board[0][0];
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i-1][0]+board[i][0];
        }
        for(int i=1;i<m;i++){
            dp[0][i]=dp[0][i-1]+board[0][i];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
                dp[i][j]+=board[i][j];
            }
        }
        return dp[n-1][m-1];
    }
}

发表于 2018-10-11 00:20:32 回复(0)

wumingde110

class Bonus {
public:
int getMost(vector<vector<int> > board) {
// write code here
vector <int> result(6,0);
for(int i=0;i<6;i++)
{
result[i]=result[i-1]+board[0][i];
}
for(int xx=1;xx<6;xx++)
{
for(int i=0;i<6;i++)
{
if(i==0)
{
result[i]+=board[xx][i];
}
else
{
result[i-1]>result[i]?result[i]=result[i-1]+board[xx][i]:result[i]=result[i]+board[xx][i];
}
}
}

return result[5];
}
};

发表于 2018-08-27 16:26:56 回复(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)

C/C++

哦哦哦5

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        //动态规划
        vector<vector<int>> dp(6, vector<int>(6));
        dp[0][0] = board[0][0];
        for(int i = 1; i < 6; i++)
        {
            dp[0][i] = board[0][i] + dp[0][i-1];
            dp[i][0] = board[i][0] + dp[i-1][0];
        }
        
        for(int i = 1; i < 6; i++)
        {
            for(int j = 1; j < 6; j++)
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        }
        return dp[5][5];
    }
};

发表于 2018-08-04 22:04:52 回复(0)