Python递归法计算棋盘上所有路径总奖品最大值（京东2016编程题）

问题描述：假设有一个6x6的棋盘，每个格子里有一个奖品（每个奖品的价值在100到1000之间），现在要求从左上角开始到右下角结束，每次只能往右或往下走一个格子，所经过的格子里的奖品归自己所有。问最多能收集价值多少的奖品。

思路：每个格子所在路径的总奖品最大值依赖于左边的格子或右边的格子。

from random import randrange

def generateRandomValues(m, n):

    #生成含有随机奖品价值的m*n棋盘

    values = [[randrange(100, 1000) for i in range(m)] for j in range(n)]

    return values

def maxValues(values, m, n):

    #使用递归算法计算总奖品最大值

    #如果不在表格范围之内，返回0

    if m<0 or n<0:

        return 0

    else:

        #否则，返回前两个位置所在路径的最大总奖品价值和当前位置奖品的和

        return max(maxValues(values, m-1, n), maxValues(values, m, n-1)) + values[m][n]

def output(values, n):

    #打印表格

    formatter = '----'*n+'\n|'

    for i in range(n):

        formatter += '{0['+str(i)+']}|'

    for item in values:

        print(formatter.format(item))

    print('----'*n)

n = 6

values = generateRandomValues(n, n)

output(values, n)

print(maxValues(values, n-1, n-1))

两次运行结果：