题目描述

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

题目解读

• 剑指Offer 233
• 思路一，递归，很好理解，但是没思路二快，递归肯定比循环耗时多
• 思路二，书上思路，书上讲解的很详细，但是貌似有点不好理解，建议自己动手画图，加强理解
• 思路三，循环实现，二维数组

代码

• 思路一，递归实现，第二轮实现的

class Solution {
public:
    int movingCountCore(int *giftMatrix, int rows, int cols, int row, int col){
        int xia = 0, you = 0;
        int result = 0;

        // 向下
        if(row < rows-1){
            xia = movingCountCore(giftMatrix, rows, cols, row+1, col);
        }

        // 向右
        if(col < cols-1){
            you = movingCountCore(giftMatrix, rows, cols, row, col+1);
        }
        
        result = xia > you ? xia : you;
        return result + giftMatrix[row * cols + col];
    }

    int movingCount(int *giftMatrix, int rows, int cols){
        if(rows <= 0 || cols <= 0){
            return 0;
        }
        return movingCountCore(giftMatrix, rows, cols, 0, 0);
    }
};

int main(){
    int giftMatrix[] = {1, 10, 3, 8, 12 , 2, 9, 6, 5, 7, 4, 11, 3, 7, 16, 5};
    int rows = 4; 
    int cols = 4;
    Solution ss;
    cout<<ss.movingCount(giftMatrix, rows, cols);
}

• 思路二，书上

#include<iostream>
using namespace std;

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){
            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];
            }
        }

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

        return max_value;
    }
};

int main()
{
    Solution ss;
    int rows = 4; 
    int cols = 4;
    int present[16] = {1, 10,  3,  8, 
                      12,  2,  9,  6, 
                       5,  7,  4, 11, 
                       3,  7, 16,  5};

    cout<<ss.max_gift(present, rows, cols)<<endl;
}

• 思路三，循环

class Solution {
public:
    int maxValue(vector<vector<int> >& grid) {
        int rows = grid.size();
        int cols = grid[0].size();
        for (int j=1; j<cols; j++) {
            grid[0][j] += grid[0][j-1];
        }
        for (int i=1; i<rows; i++) {
            grid[i][0] += grid[i-1][0];
        }
        for (int i=1; i<rows; i++) {
            for (int j=1; j<cols; j++) {
                grid[i][j] += std::max(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[rows-1][cols-1];
    }
};

总结展望

• 思路二更为强大，思路一递归实现更为简洁

我是分割线，我是分割线，我是分割线

• 附第一轮递归实现，第二轮看的时候感觉好垃圾啊，代码写的不好，不删除是因为见证自己的成长吧

#include<iostream>
using namespace std;

class Solution {
public:

    int max_gift_core(int *present, int rows, int cols, int row, int col){
        int you = 0;
        int xia = 0;
        int result = 0;

        // 向右
        if (col < cols-1){
            you =  present[row * cols + col+1];   
        }

        // 向下
        if (row < rows-1){
            xia = present[(row+1) * cols + col];
        }

        if (you > xia){
            result = max_gift_core(present, rows, cols, row, col+1);
        }
        else if(xia > you){
            result = max_gift_core(present, rows, cols, row+1, col);
        }
        else{ // you = xia，分情况讨论
            if (you != 0){ // 两个格子礼物价值相等且不为0，此时向右向下均可，此处选择向右
                result = max_gift_core(present, rows, cols, row, col+1);
            }
            else{ // 到达最右下角you=xia=0，递归结束
                result = 0;
            }
        }

        return present[row * cols + col] + result;
    }

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

        return max_gift_core(present, rows, cols, 0, 0);
    }
};

int main()
{
    Solution ss;
    int rows = 4; 
    int cols = 4;
    int present[16] = {1, 10,  3,  8, 
                      12,  2,  9,  6, 
                       5,  7,  4, 11, 
                       3,  7, 16,  5};

    cout<<ss.max_gift(present, rows, cols)<<endl;
}

• 对于应用递归思想，是有点小问题的，每次求出的并不一定就是全局最优解，关于这一点还需要探究
  关于这一点在第二轮思考应该是在判断两者相等时，直接向下向右均可导致的，直接看第二轮的递归实现吧