1. A method for solving problems by breaking them down into simpler, overlapping subproblems and solving them independently. (Optimal substructure)

2. The solutions to the subproblem are stored in memory (typically in an array or hash table) and reused to solve the larger problem. (Overlapping subproblems)

==> Lead to significant improvements in performance compared to solving the problem from scratch each time.

1. Break Down: Divide the main problem into smaller, more manageable subproblems.

2. Solve Subproblems: Find solutions to these subproblems.

3. Store Results: Store the results of each unique subproblem (memoization or tabulation).

4. Reuse Results: When you encounter the same subproblem again, use the stored result.

5. Combine: Combine the solutions of the subproblems to get the solution for the original, larger problem.

1. Memoization (Top-Down Approach):

   • Starts with the original problem and breaks it down recursively.

   • If a subproblem is encountered for the first time, its solution is computed and stored (memoized).

   • If the same subproblem is encountered again, the stored result is returned directly without re-computation.

   • Often implemented using recursion with a lookup table (like a hash map or array).

2. Tabulation (Bottom-Up Approach):

   • Starts by solving the smallest possible subproblems first.

   • Solves subproblems iteratively, building up solutions to larger and larger subproblems.

   • Typically uses an array or table to store results in a specific order.

   • The solution to the original problem is usually the last entry computed in the table.

   • Avoids recursion overhead but requires careful planning of the order of computation.

Example: Imagine you need to calculate the 10th Fibonacci number (F(10)):

Naive Case: Recursive O(2^n)

def fib_naive(n): 

if n <= 1: 

return n 

else: 

return fib_naive(n-1) + fib_naive(n-2)

1. Memoization (Top-Down):

• • • You ask for F(10).

    • The function sees it needs F(9) and F(8). It makes recursive calls for those.

    • F(9) needs F(8) and F(7), and so on.

    • Whenever a value like F(3) is computed, it's stored.

    • Later, when another call needs F(3), the stored value is returned instantly instead of recomputing.

    • It's like calling a manager (F(10)) who delegates tasks (F(9), F(8)) down the chain, and everyone writes down their answer once done so they don't have to figure it out again.

# Python implementation using Memoization

def fib_memo_helper(n, memo):

# 1. Base cases

if n <= 1:

  return n

# 2. Check if already computed

if memo[n] != -1:

  return memo[n]

# 3. Compute, store, and return

memo[n] = fib_memo_helper(n - 1, memo) + fib_memo_helper(n - 2, memo)

return memo[n]

def fib_memoization(n):

if n < 0:

  raise ValueError("Input must be a non-negative integer")

# Initialize memoization table of size n+1 with -1 (or None)

memo = [-1] * (n + 1)

return fib_memo_helper(n, memo)

# Example usage:

n = 10

print(f"Memoization F({n}) = {fib_memoization(n)}") 

# Output: Memoization F(10) = 55

2. Tabulation (Bottom-Up):

• • • You know you need F(10). You also know the base cases F(0)=0 and F(1)=1.

    • You create a table (e.g., an array dp of size 11).

    • You fill it from the start: dp[0]=0, dp[1]=1.

    • Then you calculate dp[2] = dp[1] + dp[0].

    • Then dp[3] = dp[2] + dp[1].

    • ...you continue iteratively until you calculate dp[10] = dp[9] + dp[8].

    • It's like starting with the basic ingredients (F(0), F(1)) and building up step-by-step until you reach the final product (F(10)).

# Python implementation using Tabulation 

def fib_tabulation(n): 

if n < 0: 

raise ValueError("Input must be a non-negative integer") 

if n <= 1: 

return n 

# 1. Initialize table of size n+1 

dp_table = [0] * (n + 1) 

# 2. Set base cases 

dp_table[0] = 0 

dp_table[1] = 1 

# 3. Fill the table iteratively from 2 up to n 

for i in range(2, n + 1): 

dp_table[i] = dp_table[i - 1] + dp_table[i - 2] 

# 4. The final answer is in dp_table[n] 

return dp_table[n] 

# Example usage: 

n = 10 

print(f"Tabulation F({n}) = {fib_tabulation(n)}") 

# Output: Tabulation F(10) = 55

1. Advantages: Dynamic programming guarantees an optimal solution by avoiding redundant calculations and exploring all possible subproblems.

2. Disadvantages: It might require a significant amount of memory to store solutions to subproblems in a table. In some cases, identifying the optimal substructure and recursive relation can be challenging.

1. Fibonacci Sequence: Compute the n^th Fibonacci number efficiently using a table to store previously computed values.

2. Longest Common Subsequence: Find the longest subsequence that appears in two sequences.

3. Knapsack Problem: Determine the maximum value that can be obtained by selecting items with given weights and values, subject to a weight constraint.

4. Matrix Chain Multiplication: Determine the optimal order of multiplying a sequence of matrices to minimize the number of scalar multiplications.

5. Edit Distance: Calculate the minimum number of operations (insertions, deletions, substitutions) required to transform one string into another.

6. Optimal Binary Search Trees

7. Rod Cutting Problem

8. Longest Increasing Subsequence

9. Coin Change Problem