What is Overlapping Subproblems ?

A problem can be categorized as overlapping subproblem if any same subproblems used to solve bigger problems. For example, look the Graph Subproblem of fibbonaci series below. We know that the general formula to solve fibonacci series is Fn=F(n-1)+F(n-2) for n≥2

Figure 1 Graph Subproblem of Fibonacci Series With Noticed Overlapping Subproblems

From the graph above, there is repetation on F2 calculation. Because calculation of F3 and F4 need to F2 value, the naïve method may need twice or more calculation of F2. The naïve method would do that repetation for every found subproblems that caused high exection time and use of memory. The algorithm to find the n-sequence of fibonacci series should be

1 2 3 4 5 6

Function Fibo(n) if n<2 then return 1 else return Fibo(n-1) + Fibo(n-2) end

If we want to know the five sequence (n=5), then the algorithm above would produce the call tree described below:

1. Fibo(5) 
2. Fibo(4)+Fibo(3)
3. (Fibo(3)+Fibo(2))+(Fibo(2)+Fibo(1))
4. (Fibo(2)+Fibo(1))+(Fibo(1)+Fibo(0))+((Fibo(1)+Fibo(0))+Fibo(1)
5. ((Fibo(1)+Fibo(0))+Fibo(1))+(Fibo(1)+Fibo(0))+((Fibo(1)+Fibo(0))+Fibo(1)) 

From described call tree above, call of Fibo(2) repeated three time. Then if we increase n value, more repeated of subproblem will called. Thus, the execution time will increase exponentially.