Skip to content

Overlapping subproblems

一、重叠子问题

二、如何快速判断是否存在"Overlapping subproblems"?以"relation-structure-computation"、"结构化思维" 来思考:

1、在recursion activation tree中,存在着多个值相等的节点、多条到达相同值的path,在下面的"非常形象的说明"章节中,就形象地展示了这样的情形。

2、通过对recurrence relation进行简单的推演,画出其recursion activation tree,通过规则1来进行判断;在下面的"非常形象的说明"章节中,就给出了这样的案例。

wikipedia Overlapping subproblems

In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.[1][2] [3]

For example, the problem of computing the Fibonacci sequence exhibits overlapping subproblems. The problem of computing the n*th Fibonacci number *F(n), can be broken down into the subproblems of computing F(n − 1) and F(n − 2), and then adding the two. The subproblem of computing F(n − 1) can itself be broken down into a subproblem that involves computing F(n − 2). Therefore, the computation of F(n − 2) is reused, and the Fibonacci sequence thus exhibits overlapping subproblems.

A naive recursive approach to such a problem generally fails due to an exponential complexity. If the problem also shares an optimal substructure property, dynamic programming is a good way to work it out.

非常形象的说明

labuladong 经动态规划:编辑距离 # 暴力破解的重叠子问题

还有点小问题就是,这个解法是暴力解法,存在重叠子问题,需要用动态规划技巧来优化。

怎么能一眼看出存在重叠子问题呢?前文 动态规划之正则表达式 有提过,这里再简单提一下,需要抽象出本文算法的递归框架:

def dp(i, j):
    dp(i - 1, j - 1) #1
    dp(i, j - 1)     #2
    dp(i - 1, j)     #3

对于子问题dp(i-1,j-1),如何通过原问题dp(i,j)得到呢?有不止一条路径,比如dp(i,j)->#1dp(i,j)->#2->#3。一旦发现一条重复路径,就说明存在巨量重复路径,也就是重叠子问题。

NOTE:

1、上述是快速的推演方法

labuladong 动态规划详解 # 一、斐波那契数列

斐波那契数列的数学形式就是递归的,写成代码就是这样:

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

PS:但凡遇到需要递归的问题,最好都画出递归树,这对你分析算法的复杂度,寻找算法低效的原因都有巨大帮助。

观察递归树,很明显发现了算法低效的原因:存在大量重复计算,比如f(18)被计算了两次,而且你可以看到,以f(18)为根的这个递归树体量巨大,多算一遍,会耗费巨大的时间。更何况,还不止f(18)这一个节点被重复计算,所以这个算法及其低效。

这就是动态规划问题的第一个性质:重叠子问题。下面,我们想办法解决这个问题。