Types of Dynamic Programming

Dynamic Programming is divided into two main approaches: top-down (memoization) and bottom-up (tabulation).

1 Memoization (Top-down Dynamic Programming)

Think of it like starting at the top of a tree and working your way down to the leaves. It is also known as caching in dp.

In memoization, we start the given problem by breaking it down into smaller subproblems. We then solve these subproblems recursively and store their results. If the same subproblem occurs again, instead of solving it repeatedly, we return the saved result.

How does Memoization Work?

The basic idea behind memoization is to:

1. Identify repetitive subproblems.
2. Store the results of these subproblems in memory.
3. Check if the result of a subproblem is already computed before solving it again.

Example: Fibonacci Sequence Calculation Using Memoization

#include <iostream>
#include <vector>

using namespace std;

int fib(int n, vector<int> &dp){
	// base case
	if(n<=1){
		return n;
	}
	
	//step 3
	if(dp[n] != -1){
		return dp[n];
	}
	
	// Step 2
	dp[n] = fib(n-1) + fib(n-2);
	return dp[n];
}

int main(){
	int n = 5;
	
	vector<int> dp(n+1);
	
	for(int i = 0; i<= n; i++){
		dp[i] = -1;
	}
	
	cout<<fib(5, arr);
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(n)
  • O(n) because of vector/array
  • O(n)because of recursive calls
  • Overall, O(2n)  ~ O(n)

2 Tabulation (Bottom-Up Approach)

Tabulation is a bottom-up approach to dynamic programming. Unlike memoization, which uses a top-down approach and stores the results of subproblems in memory, tabulation starts from the base case and iteratively builds up solutions to larger subproblems.

How does Tabulation Work?

The basic idea behind tabulation is to:

1. Identify the base cases and create a table to store their results..
2. Fill the table iteratively, solving each subproblem based on previously solved subproblems.
3. Use the values in the table to solve the original problem.

Steps to Convert Recursion to Tabulation:

1 Create dp array

dp(n+1);

2 Initialize base cases, and initialize them in the dp array

dp[0] = 0;
dp[1] = 1;

3 Use a for loop to calculate the values and fill in the array

	for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Fill table iteratively
    }

4 return the nth index of array.

return dp[n];

Example: Fibonacci Sequence Calculation using Tabulation

Let's consider the problem of calculating Fibonacci numbers using tabulation. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

#include <iostream>
#include <vector>

long long fibonacci(int n) {
    std::vector<long long> dp(n + 1, 0); // Tabulation table
    dp[0] = 0; // Base case
    dp[1] = 1; // Base case
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Fill table iteratively
    }
    return dp[n]; // Solution to original problem
}

int main() {
    int n = 50;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

Complexity Analysis

• Time Complexity:O(n)
  • We iterate from 1 to n to fill up the dp array.
• Space Complexity:O(n)
  • We use an array of size n+1 to store the result of subproblems.

Comparison

1. Approach:
   1. Memoization:
      1. Top-down approach.
      2. Uses recursion to solve subproblems.
   2. Tabulation:
      1. Bottom-up approach.
      2. Solves subproblems iteratively without recursion.
2. Memory Usage:
   1. Memoization:
      1. Utilizes additional memory for storing the results of subproblems.
      2. Requires memory for function call stack due to recursion.
   2. Tabulation:
      1. Requires memory for the table used to store results.
      2. Does not require additional memory for recursive calls.
3. Performance:
   1. Memoization:
      1. Can be slower due to function call overhead and memory lookups.
      2. Efficient for problems with a large number of overlapping subproblems.
   2. Tabulation:
      1. Usually faster due to the absence of recursion and direct access to table values.
      2. More efficient for problems where all subproblems need to be solved.
4. Use Cases:
   1. Memoization:
      1. Suitable for problems where the number of unique subproblems is small.
      2. Useful when you need to avoid solving the same subproblem multiple times.
   2. Tabulation:
      1. Suitable for problems where all subproblems need be solved and the problem can be divided into overlapping subproblems.
      2. Particularly efficient when the entire solution space can be represented as a table.

3 Space Optimization

To optimize space complexity, we can avoid using memoization map and store only the necessary results in variables.

Conversion from tabulation to Space Optimization

• Replace:

dp[1] with prev1
dp[0] with prev2

dp[i] = dp[i - 1] + dp[i - 2];

current = prev1 + prev2

• Shifting:

shift prev2 forward to prev1 i.e prev2 = prev1

shift prev1 to current i.e prev1 = current

• Return:

now prev1 is pointing to the required sum, just return it.

Complete Code:

#include <iostream>
#include <vector>

long long fibonacci(int n) {
    std::vector<int> dp(n + 1, 0); // Tabulation table
   	prev1 = 1; // Base case
    prev2 = 0; // Base case
    
    if(n==0){
    	return prev2;
    }
   	
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2 // Fill table iteratively
        
        // shift logic
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1; // return prev1
}

int main() {
    int n = 50;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(1)