首页 > 试题广场 > 年终奖
[编程题]年终奖

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

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

156个回答

添加回答
//基于动态规划的思想,不仅仅局限于6*6矩阵,适用于所有的N*M矩阵以及所有的方阵。
public int getMost(int[][] board) {  
        //两个for循环用来遍历二维数组不用多说。
        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[i][j] += board[i][j-1];
                }else if(j == 0){
                    //如果走在列的临界边,也就是第一列,那么他只能向下走
                    //向下走的时候该点就要将上面的值加起来。
                    board[i][j] += board[i-1][j];
                }else{
                    //核心点在这,除去两个临界边,剩下的就是既能向右走,也能向下走,
                    //那么这时候就要考虑走到当前点的所有可能得情况,也就是走到当前点
                    //各自路径的和是不是这些所有到达该点路径当中最大的了。
                    //temup用来存储从该点上面走下来的最大路径和。
                    //templeft用来存储从该点左边走过来的最大路径的和,
                    int temup = board[i-1][j];
                    int templeft = board[i][j-1];
                  //这两者肯定只能选其一,进行比较,那个大,就把这个值加给当前点,
                  //因为从一开始我们就进行了大小的比较,每一个点存储的都是到达当前点
                  //的最大值。所以直到最后一个点为止,她的值就是当前最大值的和。只要返回
                  //最后一个点的内容就可以了。
                    if(temup>templeft){
                        board[i][j] +=temup ;
                    }else{
                        board[i][j] +=templeft;
                    }
                }
            }
        }
        /*  初始数组的情况。
            564 448 654 186 490 699 
            487 444 563 228 365 261 
            429 505 612 564 715 726 
            464 617 234 647 702 263 
            245 249 231 462 453 646 
            669 510 492 512 622 135  
         */
        /*结束后返回的数组。
        564     1012    1666    1852    2342    3041    
        1051    1495    2229    2457    2822    3302    
        1480    2000    2841    3405    4120    4846    
        1944    2617    3075    4052    4822    5109    
        2189    2866    3306    4514    5275    5921    
        2858    3376    3868    5026    5897    6056
        可以看到,最后一个坐标点的值6056,他就是当前最优的路径所得出来的值
         */
        return  board[board.length-1][board[0].length-1];
    }

编辑于 2016-08-23 15:00:27 回复(22)

平面上有N*M个格子,每个格子中放着一定数量的苹果。你从左上角的格子开始, 每一步只能向下走或是向右走,每次走到一个格子上就把格子里的苹果收集起来, 这样下去,你最多能收集到多少个苹果。

解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”, 第二步找到“状态转移方程”,然后基本上问题就解决了。

首先,我们要找到这 个问题中的“状态”是什么?我们必须注意到的一点是, 到达一个格子的方式最多只有两种:从左边来的(除了第一列)和从上边来的(除了第一行)。 因此为了求出到达当前格子后最多能收集到多少个苹果, 我们就要先去考察那些能到达当前这个格子的格子,到达它们最多能收集到多少个苹果。 (是不是有点绕,但这句话的本质其实是DP的关键:欲求问题的解,先要去求子问题的解)

经过上面的分析,很容易可以得出问题的状态和状态转移方程。 状态S[i][j]表示我们走到(i, j)这个格子时,最多能收集到多少个苹果。那么, 状态转移方程如下:

S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)

其中i代表行,j代表列,下标均从0开始;A[i][j]代表格子(i, j)处的苹果数量。

S[i][j]有两种计算方式:1.对于每一行,从左向右计算,然后从上到下逐行处理;2. 对于每一列,从上到下计算,然后从左向右逐列处理。 这样做的目的是为了在计算S[i][j]时,S[i-1][j]和S[i][j-1]都已经计算出来了。


参考网上的。
发表于 2016-08-17 11:20:00 回复(0)
import java.util.*;

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

发表于 2015-10-10 16:19:30 回复(4)
动态规划的思想,arr[i][j]记录着到 i j 最多的奖金
import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        // write code here
        int[][] arr = new int[6][6];
        for(int i = 0;i<6;i++){
        	for(int j = 0;j<6;j++){
        		int b = board[i][j];
        		if(i==0&&j==0)
        			arr[i][j] = b;
        		else if(i==0){
        			arr[i][j] = arr[i][j-1]+b;
        		}else if (j==0) {
					arr[i][j] = arr[i-1][j]+b;
				}else{
					arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j])+b;
				}
        	}
        }
        return arr[5][5];
    }
}
发表于 2016-04-13 19:25:11 回复(1)
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)
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)
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)
class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        int p[6][6]={0};
       p[0][0]=board[0][0];
        for(int i=1;i<6;i++)
        {
        p[i][0]=p[i-1][0]+board[i][0];
        p[0][i]=p[0][i-1]+board[0][i];
        }
   
        for(int i=1;i<6;i++)
        for(int j=1;j<6;j++)
         {
   	      int a=p[i][j-1]>p[i-1][j]?p[i][j-1]:p[i-1][j];
   	      p[i][j]=a+board[i][j];
         }
         return p[5][5];
    }	
};

发表于 2015-10-20 14:32:35 回复(4)
class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        int a[7][7] = {0};
        for(int i=1;i<7;i++)
            for(int j=1;j<7;j++)
                a[i][j] = board[i-1][j-1] + max(a[i-1][j],a[i][j-1]);
        return a[6][6];
    }
};

发表于 2017-07-18 12:46:48 回复(1)
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)
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)
// 我给一个递归版本的解答。思路就是对于任意点(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:
    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)

做烂了的路径dp问题 万变不离其宗

当前点的最大总价值 = max(上面点最大总价值,左边点的最大总价值) + 当前点价值
(0, 0)点以及第一行和第一列要先初始化一波
class Bonus {
public:
    int dp[6][6];
    int getMost(vector<vector<int> > board) {
        memset(dp, 0, sizeof(dp));
        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] = max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        return dp[5][5];
    }
};
编辑于 2018-10-12 12:08:11 回复(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[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)
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)
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)
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)
//动态规划
/**
 * @Author: Usher
 * @Description:
 *  f[i][j]路径最大值
 * f[i][j] = Math.max(f[i-1][j],f[i][j-1]) + grid[i][j];
 * 上:f[i][j] = f[i-1][j] + grid[i][j];
 * 左:f[i][j] = f[i][j-1] + grid[i][j];
 * 初值:f[0][0] = grid[0][0]
 * f[0][j > 0] = f[0][j-1] + grid[0][j]//一行
 * f[i > 0][ 0] = f[i-1][0] + grid[i][0]//一列
 */
public class Solution43 {
    public int getMost(int[][] board) {
        // write code here
        int m = board.length;
        int n = board[0].length;
        int[][] f = new int[m+1][n+1];
        for (int i =0;i < m;i++){
            for (int j=0;j<n;j++){
                if (i == 0){
                    if (j == 0){
                        f[i][j] = board[i][j];
                    }else {
                        f[i][j] = f[i][j-1] + board[i][j];
                    }
                }else if (j == 0){
                    f[i][j] = f[i-1][j] + board[i][j];
                }else {
                    f[i][j] = Math.max(f[i-1][j],f[i][j-1]) + board[i][j];
                }
            }
        }
        return f[m-1][n-1];
    }
}
发表于 2018-05-09 17:22:34 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-808北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号