问题描述:假设有一个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))
两次运行结果: