稀有猿诉

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

动态规划从入门到放弃

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

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

动态规划的适用范围

最优子结构性质

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

重叠子问题性质

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

寻找状态转移方程

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

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

动态规划的分类总结

动态规划问题博大深精,甚至有人说万物皆可DP,意思是说几乎所有的题都可以用动态规划来求解。可以根据几个维度来对动态规划进行分类总结:一是看输入数据结构,是一维的数组列表,还是二维的矩阵或者树或者邻接表,当然还有双一维的输入。二是看时间复杂度是线性(即O(n))的还是二次的(即O(n2))。为什么要这样来分,因为这样分了之后就会有共性,能总结出一些经验。

还需要注意,动态规划总是要使用额外的空间来存储状态,一般来说空间复杂度与输入数据的维度是一致的,比如对于一维输入,一维的空间复杂度就够了(O(n)),即使有些会用到二维空间复杂度,但也可以优化到一维。

一维一次

也就是输入是一个一维数组,且用线性时间和线性空间就能解决的动态规划问题。这一般是入门级别的问题。

这种问题最为明显的特点是状态转移方程只跟前后相邻的元素有关系,或者最多是前前一个元素有关系,并且状态转移方程肯定只有一个参数。f(i) 通常能由f(i-1)或者f(i-2)推导而来。最最典型的例子就是爬楼梯和打家劫舍。

典型题目

题目 题解 说明
53. 最大子数组和 题解
70. 爬楼梯 题解
剑指 Offer II 091. 粉刷房子 题解
91. 解码方法 题解
152. 乘积最大子数组 题解
198. 打家劫舍 题解
213. 打家劫舍 II 题解
309. 最佳买卖股票时机含冷冻期 题解
1824. 最少侧跳次数 题解 典型一维多状态,与粉刷房子类似
题解
题解

一维二次

输入是一维,但是时间复杂度会上升到O(n2)。原因在于当前的状态f(i)与其前面的所有状态都有可能有关系,通常f(i)是前面状态的一种极值,或者累加。状态转移方向一般为f(i) = max{f(j), 0<=j<i}。因为对于每一个状态,都要遍历一次其前面的所有状态,以寻找满足某种约束条件的结果,所以时间复度会上升到O(n2)。典型的问题是背包问题和子序列问题。

背包问题是典型的一维二次问题,关于背包问题,单独总结了一篇文章

典型题目

题目 题解 说明
45. 跳跃游戏 II 题解
55. 跳跃游戏 题解
300. 最长递增子序列 题解
343. 整数拆分 题解
673. 最长递增子序列的个数 题解
873. 最长的斐波那契子序列的长度 题解
题解
题解
题解

双一维二次

输入是两个一维数组(或者序列或者字符串),因为输入是两个一维的,必然是要按个遍历一次,所以时间复杂度不可能小于二次(O(mn)),其中m和n是两个一维数组的和度。通常空间复杂度都有优化到一维。最为典型的例子就是两个字符串的最长公共子序列。

典型题目

题目 题解 说明
72. 编辑距离 题解
583. 两个字符串的删除操作 题解
1143. 最长公共子序列 题解
题解
题解

二维二次

典型题目

题目 题解 说明
62. 不同路径 题解
64. 最小路径和 题解
120. 三角形最小路径和 题解
221. 最大正方形 题解
337. 打家劫舍 III 题解
799. 香槟塔 题解
题解
题解

参考资料

Comments