leetcode-python动态规划题入门

简介: 关于动态规划,提到这个词,可能很多刷过题的测试都会感到头疼,这个难度真的是高出其他题型至少半个次元,我也不例外,要不是其他题型基本都刷光了,也不会来啃动态的题。

周六,一个简单的早上我简单的做了一道简单难度的动态规划题,这给大家简单说说,诸如上台阶的多种方法,股票买入的最佳机会,黑瞎子掰苞米的最佳收手时间,打家劫舍的 经典题型,这次的题也差不多。微信图片_20220615125937.png相信题意很简单,栅栏的柱子数 和 涂料数 都给你,让你求出一共多少种图的方法,其中有个条件,就是同一种颜色的柱子最多只能2个。也就是说 你可以:黄黄红,但是不可以黄黄黄。

针对这道题,我们可能一开始没啥思路,这里教一个小技巧,先把影响咱思维的条件删掉,看看有啥思路。也就是说,我们去掉同一种颜色柱子最多只能2根的这个设定。来考虑,那么就简单了。排列组合嘛。

假设5个柱子,3个颜色。那么每个柱子都可以涂3种情况,一共5根。那最终结果所有情况就是:3*3*3*3*3  = 3的5次方。很简单就有了主体思路,然后再加上限制条件,就是不能涂超过2根一样颜色的设定。假设只有1根 ,那么简单了。就是 3种颜色 3种结果假设只有2根,那么因为不触碰到设定最多2根所以也简单。就是3*3种结果假设有3根,这个时候才开始要考虑。前俩根的所有情况一共是 3*3 种,那么第三根呢?它有几种可以涂的情况呢?它可以这么考虑,要么只要不和第二根颜色相同,要么不和第一根颜色相同,这俩种情况都铁定不会触犯限制。不管你颜色一不一样,反正第三根满足不和第一根 或 第二根相同就好。现在让我们来看下一共的可能情况:

三根柱子:A B C

三种颜色:红 黄 蓝

A   B  C

红 红  (黄/蓝)

红 黄  (红/黄/蓝)

红 蓝  (红/黄/蓝)

黄 红  (红/黄/蓝)

黄 黄  (红/蓝)

黄 蓝  (红/黄/蓝)

蓝 红  (红/黄/蓝)

蓝 黄  (红/黄/蓝)

蓝 蓝  (红/黄)

所以结果很明显了。我们要么可以用加法观念,要么用减法观念:

3根柱子的最终结果=加法规律: 只有1根时的总结果数 * (颜色数-1)+只有2根时的总结果数*(颜色数-1)

减法规律:

3根无视规则的总结果数 - 颜色数 (不符合动态规划题意,抛弃)

给大家看一下加法观念的 代码:微信图片_20220615130206.png

这里 对 n 柱子数=0 / 1 /2 的时候 直接写死了返回值。

把最终所有的情况放进了 列表dp中(为啥叫dp?别问,大佬们都这么写)

最后返回dp最后一个元素就是最终结果了。


关于动态规划的窍门:

动态规划必然有一个列表存放 最终不同阶梯的最终结果。记住,每个结果,都是由前面最贴近的n个结果 演化出来的。也就是说你想知道 10个柱子有多少结果,你就必须知道8个柱子的结果 和9个柱子的结果。你想知道 8个柱子的结果,你就必须知道 6个柱子和7个柱子的结果。依次往前逆推,推到第一二个结果为止,这最开始的结果,你一定是闭眼睛都能知道的答案,这就是动态规划的主体思维。具体往前要推算多少种,那要看题,本题中说不能三根柱子一个颜色,那么就是需要考虑前面2个柱子。如果说不能五个一个颜色,那么你就要考虑前面4个柱子了。

如果能理解我上述所说的技巧。那么恭喜你,那些个bat等一线大厂的测试开发面试算法题,难度最复杂的题目中之一的动态规划,你可以无忧了。

所谓算法,其实考的不是你的代码水平,而是脑筋急转弯,看你灵活不灵活,对于我们普通人来说,天下算法就这么几十种题型,每种的核心解决思路我全背下来,不怕去不了bat大厂当测开。


相关文章
|
16天前
|
Python
使用Python绘制动态螺旋线:旋转动画效果
使用Python绘制动态螺旋线:旋转动画效果
18 1
|
15天前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
37 8
|
5天前
|
存储 监控 数据可视化
【Bokeh 库】Python 中的动态数据可视化
【7月更文挑战第15天】Python的Bokeh库是用于动态数据可视化的利器,它能创建交互式、现代Web浏览器兼容的图表。安装Bokeh只需`pip install bokeh`。基础概念包括Plot、Glyph、数据源和工具。通过示例展示了如何用Bokeh创建动态折线图,包括添加HoverTool。Bokeh还支持散点图、柱状图,可自定义样式和布局,添加更多交互工具,并能构建交互式应用和实时数据流更新。适用于数据探索和实时监控。
26 5
|
7天前
|
存储 分布式计算 索引
Python函数式编程入门窥探
Python本身不是一门函数式编程语言,但是它参考了一些函数式编程语言很好的地方,除了可以写出更可读的代码外。还能用它来实现一些特定功能,本身也提供了强大的注解系统和函数和对象之间的灵活调用。
|
8天前
|
算法 数据挖掘 计算机视觉
Python并查集实战宝典:从入门到精通,让你的数据结构技能无懈可击!
【7月更文挑战第17天】并查集,如同瑞士军刀,是解决元素分组问题的利器,应用于好友关系、像素聚类、碰撞检测和连通性分析等场景。本文从基础到实战,介绍并查集的初始化、查找与路径压缩、按秩合并,以及在Kruskal算法中的应用。通过并查集,实现高效动态集合操作,对比哈希表和平衡树,其在合并与查找上的性能尤为突出。学习并查集,提升算法解决复杂问题的能力。
|
9天前
|
监控 数据可视化 定位技术
这本书凭什么得到ChatGPT认可,评价其为最值得读的Python入门书
在当今这个飞速发展且高度数字化的时代,编程已经成为一项至关重要的技能,其重要性愈发凸显。而 Python 作为一种在众多领域都有着广泛应用且相对来说较为容易学习的编程语言,顺理成章地成为了许多编程初学者的热门选择。 就在昨天,图灵君在浏览豆瓣的时候突然被这样一条评论闪到,一位网友说:“ChatGPT 推荐给我的入门书”。我想这书莫不是口碑爆棚、备受好评的蟒蛇书《Python编程:从入门到实践(第3版)》吧!仔细一看还真是!
|
14天前
|
程序员 开发者 Python
Python动态属性与反射机制方式
通过反射和动态属性,Python程序员获得了巨大的权能,能在运行时访问、修改或为对象新增属性和方法,显著提高编程的智能化和适应性。内置的反射机制可能使开发者跨越编写代码时的限制,通过名称访问对象的特性、方法以及其他成员,为创建一个具有高度配置性、扩展性强大的应用程序打下基础。此外,利用getattr和setattr函数来获取和设定对象的属性,或是利用hasattr确认其是否存在某属性,甚至可以通过名字来动态地执行对象的函数。 总之,反射和动态属性对于Python的程序开发而言是重要的工具,它们不仅提供了编写效率高且灵活的代码的能力,还为构建可高度定制和扩展的应用程序提供了可能。对于熟练掌握这些
|
15天前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
|
16天前
|
Python
使用Python绘制彩虹效果:动态彩虹动画
使用Python绘制彩虹效果:动态彩虹动画
17 3
|
16天前
|
Python
Python实现万花筒效果:创造炫目的动态图案
Python实现万花筒效果:创造炫目的动态图案
19 2