In this article, you will learn to resolve the Fibonacci numbers problem by using recursive vs dynamic programming algorithms

Dynamic programming is an algorithm for solving a problem by breaking it down into subproblems of the same type with smaller input and storing the computed results of overlapping subproblems into a cache memory to reuse them and save time later

Steps to solve a dynamic programming problem

  • Break the problem into subproblems and find the optimal substructure. A problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems

  • Find overlapping subproblems

  • Use an array or hash table to cache solutions to overlapping subproblems. There are two ways to fill the cache: top-down and bottom-up

Let walkthrough below to explore in more details

Fibonacci numbers problem

  • Given a number n

  • Write an algorithm to return the Fibonacci number at n

  • Fibonacci numbers form a sequence such that each number is the sum of two preceding ones, starting from 0 and 1

Example

  • Input n=2, expected output 1

  • Input n=6, expected output 8

  • Input n=10. Expected output 55

Analysis

  • Optimal substructure

    F0 = 0, F1 = 1

    Fn = Fn-1 + Fn-2 for n > 1

  • Overlapping subproblems

    Say you'd like to calculate F3 which can be represented as below

    F3 = F2 + F1 = (F1 + F0) + F1

    F1 is calculated more than 1 time so the computed result can be cached to save time

Approach 1: Recursion

  • Use a recursive algorithm to resolve the problem with no-cache

  • Output
55  

Approach 2: Memoization/Top-down Dynamic Programming

  • Using a cache array to store computed results starting from N to 0, so-called top-down

  • Output
55  

Approach 3: Tabulation/Bottom-up Dynamic Programming

  • Using a cache array to store computed results starting from 0 to N, so-called bottom-up

  • Output
55  

Other dynamic progamming problems