题目描述
在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物?
思路分析
例如，在下面的棋盘中，如果沿着带下画线的数字的线路(1、12、5、7、7、16、5)，那么我们能拿到最大价值为 53 的礼物。
这是一个典型的能用动态规划解决的问题。我们先用递归的思路来分析。我们先定义第一个函数f(i,j)表示到达坐标为(i,j)的格子时能拿到的礼物总和的最大值。根据题目要求，我们有两种可能的途径到达坐标为(i,j)的格子:通过格子(i-1,j)或者(i,j-1)。所以f(i,j)=max(f(i-1,j),f(i,j-1))+gift[i,j]。gift[i,j]表示坐标为(i,j)的格子里礼物的价值。
尽管我们用递归来分析问题，但由于有大量重复的计算，导致递归的代码并不是最优的。相对而言，基于循环的代码效率要高很多。为了缓存中间计算结果，我们需要一个辅助的二维数组。数组中坐标为(i,j)的元素表示到达坐标为(i,j)的格子时能拿到的礼物价值总和的最大值。
代码实现
基本功能
代码优化
思路分析
接下来我们考虑进一步的优化。前面我们提到，到达坐标为(i,j)的格子时能够拿到的礼物的最大价值只依赖坐标为(i-1，j)和(i,j-1)的两个格子,因此第i-2行及更上面的所有格子礼物的最大价值实际上没有必要保存下来。我们可以用一个一维数组来替代前面代码中的二维矩阵maxValues。该一维数组的长度为棋盘的列数n。当我们计算到达坐标为(i,j)的格子时能够拿到的礼物的最大价值f(i,j)，数组中前j个数字分别是f(i,0),f(i,1),…f(i,j-1)，数组从下标为j的数字开始到最后一个数字，分别为f(i-1,j),f(i-1,j+1),…f(i-1,n-1)。也就是说，该数组前面j个数字分别是当前第i行前面j个格子礼物的最大价值,而之后的数字分别保存前面第i-1行n-j个格子礼物的最大价值。
代码实现
测试用例
功能测试(多行多列的矩阵;一行或者一列的矩阵;只有一个数字的矩阵)。
特殊输入测试(指向矩阵数组的指针为 nullptr)。
本题考点
考查应聘者用动态规划分析问题的能力。应聘者能够熟练应用动态规划分析问题是解答这道面试题的前提。
考查应聘者对递归及时间效率的理解。如果只是能够把递归分析转换为递归代码，则应聘者不一定能够通过这道题的面试。面试官期待应聘者能够用基于循环的代码来避免不必要的重复计算。