赞
踩
问题背景:刷leetcode 遇到最长回文字串问题,初看以为是变长的滑动窗口问题。尝试解决时,发现无法解决。搜索解题方法,发现大家提到了分别提到了动态规划,暴力解法,中心扩散。
各个击破,从《算法图解》开始了解动态规划,下面是看完《算法图解》动态规划章节后的总结。
目录
WHEN——何时?什么时间做?什么时机最适宜?WHERE——何处?在哪里做?
1. 动态规划是什么
动态规划 就是将问题分解成若干个相互独立的子问题,子问题解决之后,总问题也随之解决。
2. 目的是什么
目的是解决棘手的复杂问题。比如背包问题,如果使用暴力解法,复杂度达到O(2^n),动态规划通过划分网格可以降低到O(n^2)
3. 做什么工作
将总问题划分成独立的子问题,使用网格进行指标的计算。
1. 为什么要做
简单来说,可以降低复杂问题的计算复杂度。
2. 可不可以不做
如果问题能够在满足条件的情况下解决,或者有更低复杂度的算法方案。
3. 有没有替代方案
具体情况具体分析。约束条件相同下的最优化问题,还可以根据数据量的不同,选择实际时间复杂度或空间复杂度更低的方法。
下文是常见例子不同解法的复杂度分析对比。动态规划 例子与复杂度_weixin_30855099的博客-CSDN博客
下文可以进一步理解动态规划的适用原理:
为什么你不会动态规划?_lishinho的博客-CSDN博客
动态规划性质;以及遇到一个问题,为什么能够使用动态规划_wang2011210219的博客-CSDN博客
when和where 的问题即为:动态规划适合在哪些状况下使用?
1. 当总问题模式是:在给定约束条件下,找到最优解。
2. 分解出来的子问题,独立且离散。
1. 怎么做,动态规划是如何计算的
2. 如何提高效率——暂未研究,下面是一个简单讲解
解决如何降低动态规划算法时间复杂度_执念斩长河-CSDN博客
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。