剑指offer47.礼物的最大价值

在一个 m*n的棋盘每一格都有一个礼物，每个礼物都有一定的价值。从棋盘左上角开始拿礼物，每次向左或向下移动一格。最多能拿多少价值的礼物

思路：动态规划。这是一个典型的用动态规划解决的问题。先用递归思想分析。 。但是递归的代码有大量的重复问题，所以使用循环的方法。为了缓存中间计算结果，需要一个辅助的二维数组，数组中左边(i,j)的元素表示到达该坐标的格子能拿到的礼物价值总和的最大值。进一步优化，到达坐标为(i,j)的格子时能够拿到的礼物的最大价值只依赖坐标为(i-1,j)和(i,j-s)两个各自，因此 i-2行及更上面的所有格子礼物的最大价值实际上没有必要保存下来。可以用一个一维来替代前面代码中的二维矩阵。一维数组的长度位棋盘的列数 n。数组的前 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)