imported>MusikBot II: Removing protection templates from unprotected page (more info)

2025-12-26T23:34:17Z

Removing protection templates from unprotected page (more info)

← Previous revision	Revision as of 23:34, 26 December 2025
(No difference)

imported>Frap: Add category

2025-02-13T19:32:24Z

Add category

New page

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'' − 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 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]]

Overlapping subproblems - Revision history

imported>MusikBot II: Removing protection templates from unprotected page (more info)

imported>Frap: Add category