题目

牛客
在这里插入图片描述

解题思路

这道题属于贪心算法,但本质仍然是动态规划。对于这样一个棋盘,到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到,要么是前一列(i,j-1)向右移动一列得到
在这里插入图片描述
因此我们可以建立一个相同的矩阵gifts,gifts[i][j]表示从起点到i,j这一点中某条路径代表的礼物价值值总和,最终返回数值即可

这个计算过程中有三个特殊情况

  • 情况1:如果是起点,那么直接忽略即可
  • 情况2:如果处在第一行,那么由于是第一行,所以从起点走,它只可能是向右不断走得到的
  • 情况3:如果处在第一列,那么由于是第一列,所以从起点走,它只可能是向下不断走的到的

其余情况均是即可向右走,也可以向下走

代码

class Bonus {
public:
    int getMost(vector<vector<int> > board) 
    {
        // write code here
        int length=board.size();
        int width=board[0].size();
        vector<vector<int>> gifts(length,vector<int>(width,0));
        gifts[0][0]=board[0][0];
        for(int i=0;i<length;i++)
        {
            for(int j=0;j<width;j++)
            {
                if(i==0 && j==0)//情况1
                    continue;
                else if(i==0)//情况2
                    gifts[i][j]=gifts[i][j-1]+board[i][j];
                else if(j==0)//情况3
                    gifts[i][j]=gifts[i-1][j]+board[i][j];
                else//正常情况
                    gifts[i][j]=max(gifts[i-1][j],gifts[i][j-1])+board[i][j];
            }
        }

        return gifts[length-1][width-1];//返回到右下角的礼物价值值总和


    }
};

在这里插入图片描述