題目描述

小東所在公司要發年終獎，而小東恰好獲得了最高福利，他要在公司年會上參與一個抽獎游戲，游戲在一個6*6的棋盤上進行，上面放著36個價值不等的禮物，每個小的棋盤上面放置著一個禮物，他需要從左上角開始游戲，每次只能向下或者向右移動一步，到達右下角停止，一路上的格子里的禮物小東都能拿到，請設計一個算法使小東拿到價值最高的禮物。

給定一個6*6的矩陣board，其中每個元素為對應格子的禮物價值,左上角為[0,0],請返回能獲得的最大價值，保證每個禮物價值大于100小于1000。

import java.util.*;

public class Bonus {
??? public int getMost(int[][] board) {
??????? int[][] value = new int[6][6];
??value[0][0] = board[0][0];
??//先計算邊界位置的value，移動方向只有一個
??for(int i = 1 ; i < 6 ; i++){
???//計算第1列6個位置的value
???value[i][0] = board[i][0] + value[i - 1][0];
???//計算第1行6個位置的value
???value[0][i] = board[0][i] + value[0][i - 1];
??}
??//計算中間位置的value，移動方向向右或向下
??for(int i = 1 ; i < 6 ; i++){
???for(int j = 1 ; j < 6 ; j++){
????value[i][j] = board[i][j] + Math.max(value[i - 1][j] , value[i][j - 1]);
???}
??}
??return value[5][5];
??? }
}

總結

以上是生活随笔為你收集整理的华为机试---年终奖（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。