In this video, I discuss Dynamic Programming and Memoization. You can watch the video here.

You can also read the blog in text in this blog.

Memoization

Memoization is a performance optimization technique that stores previously computed results to avoid redundant calculations when solving problems. By caching these outcomes, it enhances efficiency and speeds up computations, especially in scenarios involving repetitive calculations or recursive algorithms. This approach optimizes runtime by utilizing stored values instead of recalculating them.

Example

#include <iostream>
using namespace std;

int memo[100]; // Array to store computed Fibonacci numbers

// Function to calculate Fibonacci using Memoization
int fibonacciMemo(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) {
        return memo[n]; // If the value is already calculated, return it
    }
    // If the value is not calculated, compute and store it in the array
    return memo[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
}

int main() {
    int n = 10; // Desired Fibonacci number
    fill(memo, memo + 100, -1); // Initializing memo array with -1 (uncomputed)
    cout << "The " << n << "th Fibonacci number is: " << fibonacciMemo(n) << endl;
    return 0;
}

In this code, the memo array stores calculated Fibonacci numbers, reducing redundant calculations and enhancing performance.

Dynamic Programming

Dynamic Programming is a problem-solving method used to solve complex problems by breaking them down into simpler subproblems. It works by solving these smaller subproblems just once and storing their solutions for future use, avoiding redundant computations. This approach typically involves solving problems in a bottom-up manner, starting from simpler cases and building up to the more complex ones. Dynamic Programming optimizes efficiency by reusing calculated results, drastically reducing the overall computational load. It's commonly used for optimization problems and often involves iterating through smaller instances to solve larger ones.

Example

#include <iostream>
using namespace std;

int fib[100]; // Array to store computed Fibonacci numbers

// Function to pre-process (calculate) Fibonacci numbers using Dynamic Programming
void pre_process(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2]; // Calculating Fibonacci numbers iteratively
    }
}

// Function to get Fibonacci number using Dynamic Programming
int fibonacciDP(int n) {
    return fib[n]; // Returning the pre-computed Fibonacci number
}

int main() {
    int n = 10; // Desired Fibonacci number
    pre_process(n); // Pre-calculate Fibonacci numbers up to 'n'
    cout << "The " << n << "th Fibonacci number is: " << fibonacciDP(n) << endl;
    return 0;
}

In this example, the fib array is pre-calculated using an iterative approach, enabling quick access to Fibonacci numbers for problem-solving.

Next video

In my upcoming video, I'll dive into problem-solving using DP techniques. I show exactly how to approach DP problems. I am going to do this based on the comments I received from you.

Support?

If you found this content helpful, your support means a lot. Your simple acts of liking the video and subscribing to the channel bring me so much motivation. Your support truly helps in boosting my work and encourages me to keep creating more valuable content.

Sharing your thoughts, questions, or feedback through comments not only helps me improve but also increases the visibility of this content within the Codeforces community. Let's keep the conversation lively and engaging for everyone!

Thank you for being a part of this!

Join the Discord server here to discuss these topics further, share problems, and discuss with legends I interview with.