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))

两次运行结果：