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

两次运行结果:

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2017-02-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

使用Python完成你的第一个学习项目

你是否想使用python进行机器学习但却难以入门? 在这篇教程中,你将用Python完成你的第一个机器学习项目。 在以下的教程中,你将学到: 下载并安装P...

810110
来自专栏ATYUN订阅号

如何用自己的数据训练MASK R-CNN模型

计算机一直很擅长数字处理,却苦于分析图像中的大量数据。直到最近,创建图形处理单元库已不仅仅用于游戏,现在我们可以利用数千个核心的原始力量来揭示图片背后的含义。

40760
来自专栏ATYUN订阅号

Deep Photo Styletransfer的一种纯Tensorflow实现,教你如何转换图片风格

通过深度学习,一秒钟让你的照片高大上,这是康奈尔大学和 Adobe 的工程师合作的一个新项目,通过卷积神经网络把图片进行风格迁移。项目已开源,名字叫「Deep ...

64850
来自专栏机器之心

资源 | 微软发布可变形卷积网络代码:可用于多种复杂视觉任务

选自Github 机器之心编译 编辑:吴攀 上个月,微软代季峰等研究者发布的一篇论文提出了一种可变形卷积网络,该研究「引入了两种新的模块来提高卷积神经网络(CN...

37460
来自专栏数据小魔方

ggplot2双坐标轴的解决方案

本来没有打算写这一篇的,因为在一幅图表中使用双坐标轴确实不是一个很好地习惯,无论是信息传递的效率还是数据表达的准确性而言。 但是最近有好几个小伙伴儿跟我咨询关于...

48590
来自专栏Python中文社区

基于RNN自动生成古诗

專 欄 ❈ 作者:yonggege,Python中文社区专栏作者 GitHub地址:https://github.com/wzyonggege ❈ 0. ch...

29250
来自专栏人工智能

TensorFlow实战——图像分类神经网络模型

Learn how to classify images with TensorFlow 使用TensorFlow创建一个简单而强大的图像分类神经网络模型 by...

42260
来自专栏素质云笔记

图像增强︱window7+opencv3.2+keras/theano简单应用(函数解读)

在服务器上安装opencv遇到跟CUDA8.0不适配的问题,于是不得不看看其他机器是否可以预装并使用。 . 一、python+opencv3.2安装 ope...

439100
来自专栏专知

【干货】TensorFlow实战——图像分类神经网络模型

Learn how to classify images with TensorFlow 使用TensorFlow创建一个简单而强大的图像分类神经网络模型 by...

48260
来自专栏大数据智能实战

基于tensorflow 1.0的图像叙事功能测试(model/im2txt)

作为多模态数据处理的经典,图像自动打标签(图像叙事功能)一直是一项非常前沿的技术,涉及到机器视觉,自然语言处理等模块。 幸运的是,谷歌基于tensorflow将...

65160

扫码关注云+社区

领取腾讯云代金券