本文主要是介绍刷题（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）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
