Editing Overlapping subproblems

In [[computer science]], a [[Computational problem|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.<ref>[https://books.google.com/books?id=NLngYyWFl_YC&dq=introduction+to+algorithms&pg=PP1 Introduction to Algorithms], 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. {{ISBN|0-262-03293-7}}.</ref><ref>[https://books.google.com/books?id=jUF9BAAAQBAJ&q=introduction+to+algorithms+3rd+edition Introduction to Algorithms], 3rd ed., (Cormen, Leiserson, Rivest, and Stein) 2014, p. 384. {{ISBN|9780262033848}}.</ref>
<ref>[https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/ Dynamic Programming: Overlapping Subproblems, Optimal Substructure], MIT Video.</ref>

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''&nbsp;&minus;&nbsp;1) and ''F''(''n''&nbsp;&minus;&nbsp;2), and then adding the two.  The subproblem of computing ''F''(''n''&nbsp;&minus;&nbsp;1) can itself be broken down into a subproblem that involves computing&nbsp;''F''(''n''&nbsp;&minus;&nbsp;2).  Therefore, the computation of ''F''(''n''&nbsp;&minus;&nbsp;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 time|exponential complexity]]. If the problem also shares an [[optimal substructure]] property, [[dynamic programming]] is a good way to work it out.

==Fibonacci sequence example==
In the following two implementations for calculating [[fibonacci sequence]], <code>fibonacci</code> uses regular recursion and <code>fibonacci_mem</code> uses [[memoization]]. <code>fibonacci_mem</code> is much more efficient as the value for any particular <code>n</code> is computed only once. 
{| style="width: auto;"
| <syntaxhighlight lang="python">
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

def fibonacci_mem(n, cache):
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fibonacci_mem(n - 1, cache) + fibonacci_mem(n - 2, cache)
    return cache[n]

print(fibonacci_mem(5, {}))  # 5
print(fibonacci(5))  # 5
</syntaxhighlight>
|}

When executed, the <code>fibonacci</code> function computes the value of some of the numbers in the sequence many times over, whereas <code>fibonacci_mem</code> reuses the value of <code>n</code> which was computed previously:
{|
|- 
! style="vertical-align:top;" | Recursive Version
! style="vertical-align:top;" | Memoization
|-
| style="vertical-align:top;" |
 f(5) = f(4) + f(3) = 5
        {{pipe}}      {{pipe}}
        {{pipe}}      f(3) = f(2) + f(1) = 2
        {{pipe}}             {{pipe}}      {{pipe}}
        {{pipe}}             {{pipe}}      f(1) = 1
        {{pipe}}             {{pipe}}
        {{pipe}}             f(2) = 1
        {{pipe}}
        f(4) = f(3) + f(2) = 3
               {{pipe}}      {{pipe}}
               {{pipe}}      f(2) = 1
               {{pipe}}
               f(3) = f(2) + f(1) = 2
                      {{pipe}}      {{pipe}}
                      {{pipe}}      f(1) = 1
                      {{pipe}}
                      f(2) = 1
| style="vertical-align:top;" |
 f(5) = f(4) + f(3) = 5
        {{pipe}}      {{pipe}}
        f(4) = f(3) + f(2) = 3
               {{pipe}}      {{pipe}}
               f(3) = f(2) + f(1) = 2
                      {{pipe}}      {{pipe}}
                      {{pipe}}      f(1) = 1
                      {{pipe}}
                      f(2) = 1
|}

The difference in performance may appear minimal with an <code>n</code> value of 5; however, as <code>n</code> increases, the [[computational complexity]] of the original <code>fibonacci</code> function grows exponentially. In contrast, the <code>fibonacci_mem</code> version exhibits a more linear increase in complexity.

==See also==
*[[Dynamic programming]]

== References ==
<references />

{{DEFAULTSORT:Overlapping Subproblem}}
[[Category:Articles with example Python (programming language) code]]
[[Category:Dynamic programming]]