面试题47:礼物的最大价值

题目

在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物?

解题思路

1. 理解题意，棋盘每次可以往右或者往下移动一个。那么也就是说棋盘每次有两个选择，要嘛往下移动，即沿着列(col)移动一格，要嘛往右移动，即沿着行(row)移动一格。
2. 那么怎么确定每一次应该往下移动还是往右移动使礼物的价值最大呢?
3. 若定义一个函数f(i,j)表示到达坐标为(i,j)的格子时能拿到的礼物总和的最大值。有两种可能的途径到达坐标为(i,j)的格子:往右移动(i,j-1)和往下移动(i-1,j)。
4. f(i,j)=max(f(i-1,j),f(i,j-1))+gift[i,j]。其中gift[i,j]表示坐标为(i,j)的格子里礼物的价值。

5. 也就是对于棋盘中每一个格子，都要从两方面判断取最大值。
   运行结果

   
   image.png

代码

• 动态规划

1. 定义一个数组maxValues，记录每一行往右移动时的礼物值数。up=f(i-1,j),left=f(i,j-1)
2. 最后的最大值存放在maxValues[cols-1]中，记得删除开辟的数组空间

class Solution{
  public:
    int max_gift(int *present,int rows,int cols)
    {
        if(present == NULL || rows < 1 || cols < 1)
        {
            return 0;
        }

        int* maxValues = new int[cols];//默认初始值为0

        for(int i = 0;i< rows;++i)
        {
            //cout << "每" << i << "行:" ;
            for(int j = 0;j<cols;++j)
            {
                int up = 0;
                int left = 0;

                if( i > 0)
                {
                    up = maxValues[j];
                }

                if(j > 0)
                {
                    left = maxValues[j-1];
                }
                maxValues[j] = max(up,left) + present[i*cols + j];
                //cout << " 每" << j <<"列礼物最大值:" << maxValues[j] ;
            }
            //cout << endl;
        }

        int max_value = maxValues[cols-1];
        delete[] maxValues;

        return max_value;
    }
};

• 递归

  
  递归过程

1. 因为入口(0,0)在max_gift()中，所有在判断行和列的时候只需row<rows-1即可

class Solution{
  public:
    int max_giftCore(int *present,int rows,int cols,int row,int col)
    {
        int down = 0,right = 0;
        int result = 0;
        //向下
        if(row < rows-1)
        {
            //++row;
            down = max_giftCore(present,rows,cols,row+1,col);
            cout << "第" <<row << "行礼物值" << down <<endl;
        }
        //向右
        if(col < cols-1)
        {
            //++col;
            right = max_giftCore(present,rows,cols,row,col+1);
            cout << "第" << col << "列礼物值:" << right <<endl;
        }
        result = down>right?down:right;
        return result+present[row*cols+col];
    }
    int max_gift(int *present,int rows,int cols)
    {
        if(present == NULL || rows < 1 || cols < 1)
        {
            return 0;
        }
        return max_giftCore(present,rows,cols,0,0);
    }
};

完整代码见GIthub