Year end bonus
problem ：
Xiaodong's company will give a year-end bonus , Xiaodong happens to get the highest welfare , He is going to participate in a lucky draw at the company's annual meeting , The game is in a 6
6 On a chessboard , It's on it 36 A gift of unequal value , A gift is placed on each small chessboard , He needs to start the game from the top left corner , You can only move down or right one step at a time , Stop at the lower right corner , Xiao Dong can get all the gifts in the grid along the way , Please design an algorithm to make Xiaodong get the most valuable gift .
Given a 66 Matrix of board, Each element is the gift value of the corresponding grid , The upper left corner is [0,0], Please return the maximum value you can get , Ensure that each gift is worth more than 100 less than 1000.
code ：
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]; } }
Operation results ：
Technology