本文主要是介绍刷题(8)-递归改动规(2),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
怎么知道递归计算过程中存在计算重叠子问题:(下面的方法,我也似懂非懂,将就看吧)
解答这个问题,最直观的应该是随便假设一个输入,然后画递归树,肯定是可以发现相同节点的。这属于定量分析,其实不用这么麻烦,下面我来教你定性分析,一眼就能看出「重叠子问题」性质。
先拿最简单的斐波那契数列举例,我们抽象出递归算法的框架:
def fib(n):
fib(n - 1)
fib(n - 2)
看着这个框架,请问原问题 f(n) 如何触达子问题 f(n - 2) ?有两种路径,一是 f(n) -> f(n-1) -> f(n - 1 - 1), 二是 f(n) -> f(n - 2)。前者经过两次递归,后者进过一次递归而已。两条不同的计算路径都到达了同一个问题,这就是「重叠子问题」,而且可以肯定的是,只要你发现一条重复路径,这样的重复路径一定存在千万条,意味着巨量子问题重叠。
同理,对于本问题(正则表达式匹配),我们依然先抽象出算法框架:
def dp(i, j):
dp(i, j + 2) #1
dp(i + 1, j) #2
dp(i + 1, j + 1) #3
提出类似的问题,请问如何从原问题 dp(i, j) 触达子问题 dp(i + 2, j + 2) ?至少有两种路径,一是 dp(i, j) -> #3 -> #3,二是 dp(i, j) -> #1 -> #2 -> #2。因此,本问题一定存在重叠子问题,一定需要动态规划的优化技巧来处理。
这篇关于刷题(8)-递归改动规(2)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!