年终奖问题

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个66的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。
给定一个66的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。

分析

可以确定是动态规划，假设dp[i][j]表示从[0,0]到[i,j]的最大值，有以下四种情况

  1. i == 0 && j == 0的时候，dp[i][j] = board[0][0]
  2. i == 0 && j != 0的时候，路径肯定是[i][j-1]到[i,j]的，dp[i][j] = board[i][j] + dp[i][j-1]
  3. i != 0 && j == 0的时候，和第二种情况类似，dp[i][j] = board[i][j] + dp[i-1][j]
  4. i != 0 && j != 0的时候，dp[i][j] = max{dp[i][j-1], dp[i-1][j]} + board[i][j]

最后输出dp[5][5]就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int getMost(int[][] board) {
	int max[][] = new int[6][6];
	for (int i = 0; i != 6; i++) {
		for (int j = 0; j != 6; j++) {
			if (i == 0 && j == 0) {
				max[i][j] = board[i][j];
			} else if (i == 0) {
				max[i][j] = board[i][j] + max[i][j - 1];
			} else if (j == 0) {
				max[i][j] = board[i][j] + max[i - 1][j];
			} else {
				max[i][j] = Math.max(max[i - 1][j], max[i][j - 1]) + board[i][j];
			}
		}
	}
	return max[5][5];
   }