稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

动态规划从入门到放弃

动态规划(Dynamic Programming)动态规划是用来求解具有最优子结构性质问题的一种方法。通俗的来说如果一个问题可以分成多个子问题或者分成多个步骤,每个子问题有多个解或者每个步骤有多个选择,最终求整体问题的一个最优解(最大值,最小值,方法总数,是否可行等等),这样的问题就适合用动态规划来求解。

动态规划一般可分为自顶而下式和自下而上式,自顶而下是通过递归,但因为涉及大量重复计算而导致时间复杂度过高,所以一般都是采用自下而上式,借助额外的空间来缓存子问题的解,减少重复计算从而降低时间复杂度,与记忆化搜索有点类似。

动态规划的适用范围

最优子结构性质

最优子结构特性Optimal Substructure)是指一个问题可以分成多个子问题,每个问题的最优解凑成整个问题的最优解。

重叠子问题性质

重叠子问题(Overlapping subproblems)是指一个问题可以分成多个子问题,每个子问题的解会重复使用多次,也就说后一个子问题的解需要使用到前一个子问题的解。最为典型的就是Fibonacci数列,也就是常说的自上而下的方式来实现动态规划(递归式),因为子问题重复,所以为了提升效率必须把子问题的解存储下来以防止重复计算。

寻找状态转移方程

动态规划并不像排序或者二分查找那样有具体的形式,它更是一种策略而非具体的算法,发现一个题目可以用动态规划求解时,还远远不够,要想写出代码,必须推导出来状态转移方程,这才是动态规划的核心,而动态如何定义,又如何转移要视具体的问题而定变化万千,所以说动态规划是最难的一类题,没有之一。

一般而言状态转移方程要以结果为导向,也就是说用这个方程能得到问题的解,这依然是一句废话,要通过大量的练习才能掌握。

典型题目

题目 题解 说明
题解
题解
题解
题解
题解
题解

参考资料

Comments