python实现动态规划
参考博客https://cloud.tencent.com/developer/article/1453737
学习动态规划的笔记,博客中的两个小demo都用python实现了一次。
首先从斐波那契数列入手,斐波那契数列可以看做一个简单的动态规划。求f(n) = f(n-1) + f(n-2),这个大学都学过,用一个递归即可以求出来了,而且其实也是比较直观的。比方f(100) 即可以知道事f(99) + f(98)而后一次类推一个个算出来,但是这样子有一个问题,就是复杂度极高,O(2**n),指数爆炸!我尝试在python下用这个求100的斐波那契数,就已经要算很久了。于是乎就有了改进,通过一个表记录子问题的答案。这样子 一下子复杂度就下降成线性的O(n),在python代码下100,甚至1000很快就算出来(Ps.在python种递归调用超过1000是不被允许的,需要修改配置参数。而且斐波那契1000也太大了吧),最后还有一点优化空间,就是上面的思路都是从上往下算,还可以从下网上算,这就是动态规划的思路了。可以看到斐波那契数列之和他前两个数有关,那即可以从f(1)开始计算,算道f(100),复杂度为O(1)。
有了上面例子的铺垫,开始看硬币问题。相似01背包,需要用尽可能少的硬币数目拼凑初目标金额。
终于把硬币问题的三种解法(递归/备忘录/dp)看完了,说实话递归是最容易绕进去的,因为实在存在太多的分支导致就算想要一步一步的按照逻辑走一遍马上就会乱掉。而当最后写出dp的解法后就会发现是如此的简单优雅,代码贴上去。这里尽管现在了解了,但是一定不过一段时间遗忘的,或者者换一个形式出现又不知道怎样处理了,总之还需多看啊。只需了解了动态规划的中心思想,代码是如此的简单优雅。
fib_result = {}coin_result_dict = {}import syssys.setrecursionlimit(9000000) #这里设置大少量'''递归暴力求解,O(n**2)效率低下python对递归的调用次数有限制,超过1000次就会报错,可以修改参数配置import syssys.setrecursionlimit(9000000) #这里设置大少量'''def fib(n): if n == 1 or n == 2: return 1 return fib(n-1) + fib(n-2)'''备忘录方法,通过记录子问题的解,减少计算次数复杂度O(n)'''def fib_helper(n): if n == 1 or n == 2: return 1 return result(n-1) + result(n-2)def result(n): if not n in fib_result: fib_result[n] = fib_helper(n) return fib_result[n]'''动态规划的思路,自下而上的求解'''def fib_dp(n): dp_map = {1:1,2:1} for i in range(3, n+1): dp_map[i] = dp_map[i - 1] + dp_map[i - 2] return dp_map[n]'''进一步优化,只保存前两个信息,复杂度为O(1)'''def fib_dp2(n): if n < 2: return n prev = 0 curr = 1 for i in range(1, n): sum = prev + curr prev = curr curr = sum return curr###################################################################################'''上面是斐波那契数列下面的例子是硬币组合即又c种不同面额的货币,c1,c2,c3...ck 需要组合成n元,最少需要多少个硬币递归问题的关键是状态转移方程,在这个问题中硬币数目f(n) = 1 + min{f(n - ci)|i 属于 [i,k]}''''''先用递归的方法求解'''def coin_cur(c,n): ans = sys.maxsize if n == 0: return 0 for c_single in c: if c_single > n: continue rest_amount = coin_cur(c, n - c_single) if rest_amount == -1: continue print(c_single) # 输出一个硬币队列,结合函数输出,例如3,就是最后三个数组即是所需的硬币组合 ans = min(ans, rest_amount + 1) # 注意上面的状态转移方程,此处就是比照ci1情况下和ci2情况下那种需要用到的硬币少 return -1 if ans == sys.maxsize else ans'''带备忘录的方法'''def coin_cur_help(c, n): ans = sys.maxsize if n == 0: return 0 for c_single in c: if c_single > n: continue rest_amount = coin_result(c, n - c_single) if rest_amount == -1: continue else: #print(c_single) ans = min(ans,rest_amount + 1) return -1 if ans == sys.maxsize else ansdef coin_result(c, n): if not n in coin_result_dict: coin_result_dict[n] = coin_cur_help(c, n) return coin_result_dict[n]'''动态规划'''def coin_dp(c, n): dp_map = {0:0} for i in range(1, n+1): dp_map[i] = sys.maxsize for k in dp_map: for c_single in c: if k < c_single: continue else: dp_map[k] = min(dp_map[k], 1+dp_map[k - c_single]) return dp_map[n] if dp_map[n] != sys.maxsize else -1if __name__ == '__main__': c = [5,10] n = 7 print(coin_dp(c, n))说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » python实现动态规划
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » python实现动态规划