本来我是不想写这篇文章的,毕竟讲动态规划的好文章那么多,哪轮得到我这个菜鸡来讲
但是我的执念又让我对动态规划这个算法这么多年来一直耿耿于怀
于是还是忍不住重复造了这个轮子
如果有人好奇为什么会对动态规划有经年的执念
那我就把原因写到了文章最后好了
那么标准开头:
1.什么是动态规划:
动态规划(Dynamic Programming),以下简称dp,是解决某一类问题的方法 2.第一个问题: 如何鉴定一个问题属于'某一类问题'.众所周知,计算机的本质是对'数据'进行'逻辑'运算,每次运算都会改变数据,所以每次运算间隔之间的数据就像一帧定格的动画,我虽然想管这玩意儿叫数据帧,但是数据帧这个概念已经被计算机网络协议占用了
所以还是这么说:每个计算间隔之间的所有数据构成当前的'状态'(需要说明的一点是,空值也是数据)
当我们在编程的时候,其实就是输入一个状态,然后经过一系列运算获得所求的那个状态
现在我们来把这个概念实例化为一个经典的例子:斐波那契数列
对于一个斐波那契数列,每个斐波那契数就是一个状态,每求一个新的状态,我们需要前两个状态
(ps:我们用的计算机不是量子计算机,所以在某一个时间点,计算机只有一个状态,但这并不矛盾,因为当前状态显然可以存储前两个状态甚至前N个状态)
在这个例子中,我们只需要按照固定模式从两个连续的状态就可以计算出新的状态,这种方法叫做递推.记住这个词,我们马上又会提到他
再来看一个题目:有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。求一共有多少种走法。
在这个题目中,初始状态是0级楼梯,第一次计算获得第一个状态,则是1级楼梯,或者2级楼梯,发现了吗?问题在于,每次计算可能产生复数个状态
你不能只保存当前的状态,题目要求你列出所有能达到结果的选择支,每个状态都可以转移到下次计算后的多个状态，所以解的复杂度就是指数的
如果反过来考虑,我们就得到了第一个问题的答案:当前状态可以从之前某次计算可能得到的某个或某些状态直接得到,无论之前这个状态是如何得到的,这就是动态规划适用的'某一类问题'
以此题为例,我们到达当第n级阶梯的方式无外乎有2种,一是在n-2级台阶向上2级,或者在n-1级台阶向上1级,无论之前你是怎么到达上一个阶梯的,也就是说,我们只要得到两个起始状态,就可以往后计算出新的状态,眼熟吗?没错,这就是个换皮的斐波那契数列,因此,递推其实就是最简单的动态规划
def func(x): a = 1 b = 2 for i in range(3, x+1): a, b = b, a+b return b
生动形象的讲解:
https://www.sohu.com/a/153858619_466939
这是leetcode上的一道题:
https://leetcode.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
简单的动态规划应用,应该是最简洁的答案了
class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ lst = list() for c in s: lst.append(c) if len(set(lst)) < len(lst): lst.pop(0) return len(lst)ps:我高中的时候参加信息技术奥赛的时候就跪在了动态规划的题上,所以印象相当深刻...
转载于:https://www.cnblogs.com/lorthevan/p/9936162.html
