题目(礼物的最大价值或年终奖)

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个 6*6 的棋盘上进行，上面放着 36 个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。

给定一个 6*6 的矩阵board，其中每个元素为对应格子的礼物价值,左上角为 [0,0],请返回能获得的最大价值，保证每个礼物价值大于 100 小于 1000。

注：剑指 offer 上的题目和牛客网上的题目有点小区别，仅在棋盘大小的区别，我们以牛客网的为准。

算法思路一

本题是经典的类似走迷宫，求最优解的问题，采用的方法是填表法，还有另一种叫刷表法，感兴趣可以了解一下。

这是经典的动态规划之填表法的应用。我们先定义函数 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))+board[i][j],其中 board[i][j] 为当前位置上的礼物价值。

但是，这里要特殊处理的是，除了第一个位置，第一行和第一列的每个位置只有一种到达路径，所以我们先对第一行和第一列进行填表。

其实本题，由于输入数组是由题目给定的，因此，我们不改动输入数组,否则我们可以给输入数组的第一行和第一列之前全补0，那么就把所有情况统一了，意味着不需要上述的特殊处理了，请注意此处的补 0 技巧。

填表法：所谓的填表法就是我们每达到表中的一个位置，就确定下该位置的最优解，然后走遍整个表，即填完整张表。

算法实现二

由于到达坐标为 (i,j) 的位置时，能够拿到的礼物的最大价值只依赖坐标为 (i-1,j)和 (i,j-1) 的两个位置，因此此第 i-2 行及更上面的所有位置上的礼物的最大价值实际上没有必要存储下来。我们用一维数组来记录足以。

算法实现一

算法实现二(优化版)

复杂度

算法一的时间复杂度和空间复杂度均为O(n^2)，优化后的算法，时间复杂度降为 O(n)。

参考

[1] <<剑指offer2>>
[2] 牛客网