面试题47-礼物的最大价值
题目
在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
解题思路
这是一个典型的能用动态规划解决的问题。我们先用递归的思路来分析。我们先定义第一个函数f(i,j)表示到达坐标为(i,j)的格子时能拿到的礼物总和的最大值。根据题目要求,我们有两种途径到达坐标为(i,j)的格子:通过格子(i-1,j)或者(i,j-1)。所以f(i,j)=max(f(i,j-1)f(i-1,j))+gift[i,j]。gift[i,j]表示坐标(i,j)的格子里礼物的价值。 尽管我们用递归来分析问题,但由于递归有大量的重复性计算,导致递归的代码并不是最优的。相对而言,基于循环的代码效率要高得多。为了缓存中间计算结果,我们需要一个一维辅助数组,该一维数组的长度为棋盘的列数n。因为到达坐标为(i,j)的格子时能够拿到的礼物的最大价值只依赖坐标为(i-1,j)和(i,j-1)的两个格子。
C++实现
int getGiftMaxValue2(const int *values, int rows, int cols) { if (!values || !rows || !cols) return 0; int *maxValues = new int[cols];//一维数组的内存不能申请为rows的大小,除非rows在内层循环 for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { int left = 0; int up = 0; if (i > 0) up = maxValues[j]; if (j > 0) left = maxValues[j - 1]; maxValues[j] = max(up, left) + values[i*cols + j]; } } int maxValue = maxValues[cols - 1]; delete maxValues; return maxValue; }
- 时间复杂度:O(mn),m是矩阵的行数,n是矩阵的列数。
- 空间复杂度:O(n)
同类型题
64-最小路径和
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。
解题思路
思路和面试题47-礼物的最大价值解题过程相似,只不过面试题47求的是最大值,该题求最小值,只需要把状态转移方程中的max转换为min即可。
C++实现
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m=grid.size(),n=grid[0].size(); vector<int>cols(n); int left=0,up=INT_MAX; for(int i=0;i<m;++i) { for(int j=0;j<n;++j) { if(i>0) up=cols[j]; if(j>0) left=cols[j-1]; cols[j]=min(up,left)+grid[i][j]; } } return cols[n-1]; } };
- 时间复杂度:O(m×n),m是矩阵的行数,n是矩阵的列数。
- 空间复杂度:O(n)
上一篇:
通过多线程提高代码的执行效率例子
下一篇:
动态规划——礼物的最大价值