Dynamic programming is a technique that breaks complex problems into multiple subproblems, while solving the subproblems, we store the answers of the expensive functions into data structures, so that when we face duplicate subproblems, we could access within linear time instead of recomputing, this particular action is called “memoization”.

There are two types of memoization (fibonacci sequence as an example):

%%{init: {'theme':'darkmode'}}%%
graph TB
%% Colors %%
classDef purple fill:#8e7cc3,stroke:#000,stroke-width:2px,color:#fff
classDef blue fill:#2374f7,stroke:#000,stroke-width:2px,color:#fff
classDef pink fill:#eb3dd6,stroke:#000,stroke-width:2px,color:#fff
classDef orange fill:#fc822b,stroke:#000,stroke-width:2px,color:#fff
classDef red fill:#ed2633,stroke:#000,stroke-width:2px,color:#fff
classDef green fill:#16b522,stroke:#000,stroke-width:2px,color:#fff

	A([fib5]):::orange --> B([fib4]):::blue & C([fib3]):::red
  B --> D([fib3]):::red & E([fib2])
  C --> F([fib2]) & G([fib1]) 
  D --> H([fib2]) & I([fib1])

%%linkStyle default stroke:white
%%linkStyle 0 stroke-width:4px,stroke:green%%
%%linkStyle 3 stroke:blue%%
%%linkStyle 4 stroke:blue%%

graph LR
%%{init: {'theme':'darkmode'}}%%
%% Colors %%
classDef purple fill:#8e7cc3,stroke:#000,stroke-width:2px,color:#fff
classDef blue fill:#2374f7,stroke:#000,stroke-width:2px,color:#fff
classDef pink fill:#eb3dd6,stroke:#000,stroke-width:2px,color:#fff
classDef orange fill:#fc822b,stroke:#000,stroke-width:2px,color:#fff
classDef red fill:#ed2633,stroke:#000,stroke-width:2px,color:#fff
classDef green fill:#16b522,stroke:#000,stroke-width:2px,color:#fff
D([fib2]) & E([fib1])--> C([fib3]):::red--> B([fib4]):::blue -->A([fib5]):::orange 

Comparison:

• Top-Down Approach:

  • Begins with the original problem and breaks it down into smaller subproblems recursively.
  • Memoizes the results of subproblems to avoid redundant calculations.
  • Can suffer from stack overflow for deep recursion.
  • Intuitive and easy to implement for problems with recursive definitions.

• Bottom-Up Approach:

  • Starts with the smallest subproblems and iteratively builds up to the original problem.
  • Computes solutions in a systematic order, typically using loops.
  • More efficient in terms of space complexity and avoids issues with stack overflow.
  • May require more upfront work to understand problem structure but can be easier to optimize.

Coin change

Word break