动归和递归算法讲解

简介: 动归和递归算法讲解

动规(DP 即 Dynamic Programming)说白了就是一个解决问题的思路——记忆化的,分阶段的,动态化的递推(从直接有结果的基准问题递推到最终问题)。

拿最简单的斐波那契问题举例子,一个大的问题f(n)可以被拆解为小一点的问题f(n-1)和f(n-2),……直到然后拆到最小的问题f(1)和f(2)。你可以从f(n)从大往小了算,也可以先从f(1), f(2), f(3)……从小往大了算。再比如leetcode的有个正则表达式匹配的问题,你可以把问题看做是一个大的字符串的匹配pattern,拆解为字符串的一部分匹配pattern的一部分的问题;也可以反过来先匹配一小部分,再不断让可以匹配的范围变大。

很多人把从大往小算的形式称作递归(Recursion),反过来从小往大了算称为DP。但实际上只要满足大规模问题可以拆解为小规模问题,这个思路本身就是DP的,无非是顺序不一样罢了。

动态规划就是指知道了一组小规模问题的答案后,就可以用一个方案(状态转移方程)组装成大一点规模问题的答案的做法而已。为啥叫“动态”呢,因为状态转移会和几个条件相关,而不是一开始就可以无脑写死(无脑写死的一般就是贪婪)。

术语上,从大往小算被称为”自顶向下“,而从小往大算被称为”自底向上“。尽管自顶向下和自底向上等价,但自顶向下算一个很容易发生的问题就是重复计算,比如你为了算f(5),普通的递归方式要重复计算很多很多次f(3), f(2)……。这些计算都是浪费的,实际表现比自底向上差的多(但再强调下,二者的思路没本质差别,仅仅是计算浪费不浪费的问题)。

但你可以加cache,每次递归的函数的参数都可以组装成一个cache的key。这样每次递归时,可以先检查一下cache是不是有,有了就不用算了,直接返回。这种带cache的递归DP一般被称为“记忆化搜索“。记忆化搜索与自底向上的DP计算方式在算法复杂度上理论上是一样的。但cache一般会用map,其实际的复杂度要比直接用数组的自顶向上要大,二者的O(1)是不一样的。此外记忆化搜索还会引入函数调用的开销,所以一般记忆化搜索比等价的自底向上要慢那么一丢丢。

此外自底向上的计算方式还可以优化存储,比如斐波那契计算时,计算f(n)只需要f(n-1), f(n-2),所以用两个变量就行,无须把所有的结果都记录下来。用go写可以是这样:
//代码效果参考:http://www.zidongmutanji.com/zsjx/15861.html

func fib(n int) int {
f0, f1 := 0, 1
for n > 1 {
f1, f0 = f0 + f1, f1
n--
}
return f1
}
但用记忆化搜索的方式,你是没法在计算得到f(4)后,把f(1)结果占用内存给方便的清理掉的。

DP最难的不在于自底向上还是自顶向下,而在于怎么拆问题。某些问题,如果之前没做过,你是很难想得到“这个问题还能这么拆”。不信?可以去看看LeetCode有一道“戳气球”的题目。我自己第一次看时虽然能猜到它是用DP,但打死都想不出来怎么拆,直到看了题解。因此大家想不出来DP,不是因为不知道DP的代码框架怎么做,而是拆解问题的思路实在太古怪,太反常识。这就需要刷题去多多适应。

But,这些反常识的方法也是人想出来的。此时也是去了解那些聪明人的脑洞的好机会:)。你也许会惊讶于人思维方式的差异的巨大。

在现实工程中,有些问题即便是可以DP,但因为拆解方案对于大部分人来说太难想;或者即使想出来,应用面太窄,需求小小的一个变化就会让整套方案不灵了。因此很多时候,如果复杂度的要求不那么严苛,还是用暴力要好一些。因此DP更常见于面试题里,证明候选人“知道像计算机专业从业者那样思考”。但这并不是说DP不重要,在计算机科学里,这个思路非常非常重要,只不过工程上不光要考虑算法复杂度,还要考虑可维护性问题而已。如果场景恰当,当然还是要用。比方说,“计算基金最大回撤”就可以用DP,实际上就是LeetCode里“买卖股票最佳时机”解题方案的镜像——就是一个算回撤,一个算正向收益的区别。

回到DP本身,如果觉得自顶向下的思路很舒服,那就总是先用递归实现自顶向下DP。通过后加上Cache用记忆化搜索的方式写代码。再改写成等价的自顶向上的做法。反复做几次看看思路上能不能贯通。但同时,有时也会省得写自底向上很舒服,反过来就别扭。

当然,虽然二者等价,可能会遇到很难自底向上写的问题。此时一般是很难找到一个很简单的从小到大的规律,这就不如用递归+cache。cache的规则就很简单,算过了就cache,没算过就没cache,递归调用中参数出现的规律不需要操心。

最后,递归能够在DP这个思路里支持实现自顶向下,但也不一定就用在DP里。递归适合的场景要更加广泛。比如dfs/bfs这样的搜索场景就可以用递归做。递归还可以用来做模拟,比如A对B做一件事、B又要对C和D做一件事,D又要对A和B做一件事……。用递归来实现很直观。

动态规划指的是题型,即解题思路;而递归指的是解题方法,即实现细节。

动态规划类题型一般有两种实现方式:

bottom-up 即 table-fill
top-down 即递归(recursion)
下面是这两种方式的详细举例。

方法一:bottom-up(table-fill)
//代码效果参考:http://www.zidongmutanji.com/bxxx/242816.html

function fib(n) {
const arr = [0, 1, 1];
for(let i=3; i<=n; i++) {
arr[i] = arr[i-2] + arr[i-1];
}
return arr[n];
}
时间复杂度:O(n)

空间复杂度:O(n)

这种实现方法的好处在于用空间换时间。时间优化了成了 O(n),但空间也变成了 O(n)。所以一般一维的 DP 大概会用变量来写。

function fib(n) {
let result = 1;
let first = 1;
let last = 1;
for(let i = 3; i <= n; i++) {
first = last;
last = result;
result = first + last;
}
return result;
}
时间复杂度:O(n)

空间复杂度:O(1)

这样一来空间复杂度瞬间降低了一个级别,变为常数级别 O(1)。“利润”非常可观。二维及以上的 DP 则会用滚动数组(rolling array)来优化。

方法二:top-down(recursion)

function fib(n){
if(n === 1 || n === 2){
return 1;
}else{
return fib(n-2) + fib(n-1);
}
}
这种实现方法的优势在于对于每一步看得非常明白,大家能够轻而易举地了解什么是斐波那契数列,对于理解这个结构非常有帮助。但不好的地方在于时间复杂度非常低,低到令人发指、实际应用中不可接受的地步。

Upper bound time complexity: T(n) = O(2^{n})

Tight upper bound time complexity: T(n) = O(1.6180^{n})

具体推算比较枯燥,可以看这里。

时间复杂度: O(1.6180^{n})

空间复杂度:O(1)
//代码效果参考:http://www.zidongmutanji.com/bxxx/294358.html

一种常见的优化手段就是上记忆化缓存 (Memoization)。

function fib(n, memo) {
if(n === 1 || n === 2){
return 1;
}else if(n in memo){
return memo[n];
}else{
memo[n] = fib(n-2, memo) + fib(n-1, memo);
}
return memo[n];
}
console.log(fib(8, {}));
时间复杂度:O(n)

空间复杂度:O(n)

这里由于有了 memo 不用重复运算,基本上只会跑 n 次,所以时间复杂度为 O(n),空间复杂度为 O(n)。

所以一般的动态规划问题考察中,大家会直接上最优解即 bottom-up 的 table-fill,并且用变量或者滚动数组来优化空间。但值得注意的是最优解并不意味着是最容易理解的实现方式。一般 recurision + memo(业界也叫 DFS + memo)被称为是万金油式的 DP,没有它解不了的题目。而且时间复杂度和空间复杂度都有很好的平衡。

动态规划其实就是把一个复杂的最优解问题分解成一系列较为简单的最优解问题,再将较为简单的最优解问题一步步分解,直到能够一眼看出为止。

动态规划看起来跟递归很像,不过推理逻辑正好是反过来的。递归的逻辑是:“要求得 d[m][n],先要求得 d[m-1][n-1]……”,动态规划的逻辑是:“先求得 d[m-1][n-1],再求 d[m][n]……”这是它们的主要区别。

动态规划和记忆化递归一般都是可以相互转化的。

动态规划的dp表就相当于递归中的缓存。

动态规划中的状态转移方程式就相当于递归调用。

通俗一点动态规划就是从下往上(从前向后)阶梯型求解数值。

总的来说动态规划从前向后,递归从后向前,两者策略不同,并且一般动态规划效率高于递归。

不过都要考虑初始状态,上下层数据之间的联系。

相关文章
GSEA 富集分析原理分析
本分分享了自己学习参考多篇 关于GSEA 原理的博客文献后总结的个人理解,以供参考学习
574 0
下篇:使用jenkins发布go项目到k8s,接上篇的手工体验改造为自动化发布
下篇:使用jenkins发布go项目到k8s,接上篇的手工体验改造为自动化发布
741 1
【密码学】非对称加密算法 - ECDH
由于 ECC 密钥具有很短的长度,所以运算速度比较快。到目前为止,对于 ECC 进行逆操作还是很难的,数学上证明不可破解,ECC 算法的优势就是性能和安全性高。实际应用可以结合其他的公开密钥算法形成更快、更安全的公开密钥算法,比如结合 DH 密钥形成 ECDH 密钥协商算法,结合数字签名 DSA 算法组成 ECDSA 数字签名算法。ECDH算法常常用来进行密钥的协商,协商好密钥后,用来解决上面的密钥分配问题,将对称加密的密钥安全的传到对端设备。算法加密/解密数字签名密钥交换RSA✅✅✅❌。
4087 0
|
6月前
|
微财基于 Flink 构造实时变量池
本文整理自微财资深数据开发工程师穆建魁老师在 Flink Forward Asia 2024 行业解决方案(一)专场中的分享。主要涵盖三部分内容:1) 基于 Flink 构建实时变量池,解决传统方案中数据库耦合度高、QPS 上限低等问题;2) 选择 Flink 进行流式计算的架构选型(Kappa 架构)及开发效率提升策略,通过数据分层优化开发流程;3) 实时变量池架构与多流关联优化实践,确保高效处理和存储实时变量,并应用于公司多个业务领域。
498 4
微财基于 Flink 构造实时变量池
|
10月前
|
ValueError: sleep length must be non-negative
ValueError: sleep length must be non-negative
263 3
Java语言使用DL4J实现图片分类
【6月更文挑战第14天】Java语言使用DL4J实现图片分类
219 3
Higress × OpenKruiseGame 游戏网关最佳实践
本文将演示 Higress 如何无缝对接 OKG 游戏服,并为其带来的优秀特性。
134653 52
网络安全与信息安全:防范漏洞、加强加密与提升安全意识深入探索自动化测试框架的设计原则与实践应用化测试解决方案。文章不仅涵盖了框架选择的标准,还详细阐述了如何根据项目需求定制测试流程,以及如何利用持续集成工具实现测试的自动触发和结果反馈。最后,文中还将讨论测试数据管理、测试用例优化及团队协作等关键问题,为读者提供全面的自动化测试框架设计与实施指南。
【5月更文挑战第27天】 在数字化时代,网络安全与信息安全已成为维护国家安全、企业利益和个人隐私的重要环节。本文旨在分享关于网络安全漏洞的识别与防范、加密技术的应用以及提升安全意识的重要性。通过对这些方面的深入探讨,我们希望能为读者提供一些实用的建议和策略,以应对日益严峻的网络安全挑战。 【5月更文挑战第27天】 在软件开发周期中,自动化测试作为保障软件质量的关键步骤,其重要性日益凸显。本文旨在剖析自动化测试框架设计的核心原则,并结合具体案例探讨其在实际应用中的执行策略。通过对比分析不同测试框架的优缺点,我们提出一套高效、可扩展且易于维护的自动

热门文章

最新文章

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问