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