劍指offer：禮物的最大價值

題目：禮物的最大價值
在一個m×n的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格直到到達棋盤的右下角。給定一個棋盤及其上面的禮物，請計算你最多能拿到多少價值的禮物？
如給定棋盤如下：
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
禮物的最大價值為1+12+5+7+7+16+5=53

# -*- coding: utf-8 -*-
# @Time         : 2019-07-11 9:59
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getMaxValue.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

def getMaxValue(values):
    """
    迷宮類的問題很適合用動態(tài)規(guī)劃來解決，因為前一步的選擇影響后一步的進行。
    動態(tài)規(guī)劃的題目一般是從遞歸思路分析，得到遞推公式之后，用循環(huán)編碼解決，并用數(shù)組保存中間結(jié)果。

    由于在這個棋盤中只能往右往下走，因此這道題的遞推公式為：
    f(i, j) = max(f(i-1, j), f(i, j-1)) + g(i, j)
    其中f(i, j)表示到達坐標為(i, j)的時候最大的值是多少，g(i, j)表示坐標(i, j)自身的值。

    這道題可以用一個和輸入等大小的數(shù)組來保存中間結(jié)果，但是注意到我們計算f(i, j)的時候只需要用到
    f(i-1, j)和f(i, j-1)，也就是說i-2及以上的行的值是被忽略的，那么我們就只需要保存第i行的前
    j個元素即可，而第i-1行則只需要保存從下標j開始的元素即從j到col-1.
    綜上，我們可以用一個一維數(shù)組來保存中間結(jié)果，其長度為棋盤的列數(shù)(也就是說這個數(shù)組長度和棋盤的一
    行一樣長)。這個數(shù)組前j個元素為f(i, 0), f(i, 1), ..., f(i, j-1)，
    后col-j個元素為f(i-1, j), f(i-1, j+1), ..., f(i-1, col-1)

    用圖形來表示就是
    xxxxx
    xxooo
    ooMxx
    xxxxx
    其中M為待求最大值的位置，我們這個數(shù)組就保存了o表示的這些元素。
    也就是當求M的時候，用它的左邊一個和上面一個元素，即左邊=maxValue[j-1]，右邊=maxValue[j]
    """
    if not values or not values[0]:
        return 0

    row, col = len(values), len(values[0])
    maxValues = [0] * col
    for i in range(row):
        for j in range(col):
            up = left = 0
            # 棋盤的第一行和第一列的最大值就是其本身
            if i > 0:
                up = maxValues[j]
            if j > 0:
                left = maxValues[j - 1]
            maxValues[j] = max(up, left) + values[i][j]

    return maxValues[col - 1]

def main():
    values = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]
    print(getMaxValue(values))

if __name__ == '__main__':
    main()