annual bonus （ dynamic programming ）（ daily practice ）



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 6*6 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.

class Bonus { public: int getMost(vector<vector<int> > board) {
if(board.empty()) { return 0; } vector<vector<int>> a=board; for(int
i=1;i<a.size();i++) { a[i][0]=a[i-1][0]+a[i][0]; } for(int
i=1;i<a[0].size();i++) { a[0][i]=a[0][i-1]+a[0][i]; } for(int
i=1;i<a.size();i++) { for(int j=1;j<a[0].size();j++) { if(a[i-1][j]>a[i][j-1])
{ a[i][j]=a[i-1][j]+a[i][j]; } else { a[i][j]=a[i][j-1]+a[i][j]; } } } return
a[5][5]; } };
 

Technology
©2020-2025 ioDraw All rights reserved, Privacy Policy