What is dynamic programming?
Dynamic programming, an innovative algorithmic approach introduced by Richard Bellman in 1950, aims to make recursion smarter and more efficient. In standard recursion, we often solve the same subproblem multiple times when it appears repeatedly in the recursion tree, leading to redundant calculations. Dynamic programming tackles this inefficiency by ensuring that each subproblem is solved only once, even if it recurs throughout the recursion tree, dramatically improving performance.
Richard Bellman is an American mathematician who invented dynamic programming on 1950.
From where the name dynamic programming came from?
Today, the word “programming” refers to writing computer applications or programs, but back in 1950, it meant planning or scheduling. The term “dynamic programming” emerged because the method focuses on planning to avoid solving the same problem multiple times. In essence, dynamic programming is recursion without repetition of the work.
Fibonacci Series Generation: Recursion vs. Dynamic Programming
When using a recursive approach to calculate the Fibonacci sequence, we compute f(4), which depends on f(3) and f(2). Each of these further depends on the two preceding numbers in the sequence. This process continues until we reach the leaf nodes, or base cases, in the recursion tree. The resulting recursion tree, as shown in the image below, reveals a key inefficiency: f(2) is calculated twice, f(1) appears three times, and f(0) shows up twice. This redundancy highlights the problem dynamic programming aims to solve.
