动态规划之-----年终奖

题目解析:

AC代码：

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));//创建二维数组，初始位为0
       dp[0][0]=board[0][0];//将第一个初始值赋值
       for(int i=0;i<row;i++){
           for(int j=0;j<col;j++){
               //1.如果是在起始位置上
               if(i==0 && j==0)
                    continue;
                if(i==0)//说明是同一行从左边过来的  那么肯定是在第一行
                    dp[i][j]=dp[i][j-1]+board[i][j];
                else if(j==0) //说明是同一列的上一行下来的
                    dp[i][j]=dp[i-1][j]+board[i][j];
                else    
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])+board[i][j];

           }
       }
        return dp[row-1][col-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

通过这题，我们更应该对动态规划了解深透！
如有错误，多多指教！