动态规划——礼物的最大价值
1.问题描述
在一个m*n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(大于0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格,直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例1:
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出:12 解释:路径1——3——5——2——1可以拿到最大价值的礼物.
2.解决方案
这个问题与找三角形的最小路径在本质上是一样的问题,可以用动态规划算法解决。
用count[ i ][ j ] 表示从左上角到第i行第j列这个格子拿到的最大的礼物价值。
(1)自顶向下 考虑从左上角出发,计算出到每个棋盘格的最大礼物价值。
一般情况下,有递推公式: count[ i ][ j ] = max{ count[ i ][ j-1 ], count[ i - 1 ][ j ] }+grid[ i ][ j ] 对于特殊情况,即 i = 0 或 j = 0 时进行特殊处理。
int maxValue(vector<vector<int>>& grid) { int rows=grid.size(); int cols=grid[0].size(); vector<vector<int>> count(rows); count[0].push_back(grid[0][0]);//初始化count数组 for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { if(i==0&&j==0) ;//前面已经进行过初始化了 else if(i==0) count[i].push_back(count[i][j-1]+grid[i][j]; else if(j==0) count[i].push_back(count[i-1][j]+grid[i][j]; else count[i].push_back(max(count[i-1][j],count[i][j-1])+grid(i,j)); } } return count[rows-1][cols-1]; }
(2)自底向上 考虑从右下角出发,计算出到每个棋盘格的最大价值。
一般情况下,有递推公式: count[ i ][ j ] = max{ count[ i ][ j+1 ], count[ i + 1 ][ j ] }+grid[ i ][ j ] 对于某些 i, j 进行特殊处理。
int maxValue(vector<vector<int>>& grid) { int rows=grid.size(); int cols=grid[0].size(); vector<vector<int>> count(rows); for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) count[i].push_back(0);//初始化count数组,方便后面的操作 count[rows-1][cols-1]=grid[rows-1][cols-1]; for(int i=rows-1;i>=0;i--) { for(int j=cols-1;j>=0;j--) { if(i==rows-1&&cols-1) ; else if(i==rows-1) count[i][j]=count[i][j+1]+grid[i][j]; else if(j==cols-1) count[i][j]=count[i+1][j]+grid[i][j]; else count[i][j]=max(count[i+1][j],count[i][j+1])+grid[i][j]; } } return count[0][0]; }