Top-down Approach

The top-down approach, also known as the recursive approach, is one of the two common approaches in dynamic programming. It involves breaking down a problem into smaller subproblems and solving them recursively.

In the context of dynamic programming, the top-down approach starts with the original problem and recursively solves smaller subproblems until reaching the base case. The solutions to the subproblems are stored in a memoization table, so that they can be reused when needed.

The top-down approach is typically implemented using recursion and memoization. Memoization involves storing the solutions to subproblems in a data structure, such as an array or a hash table, to avoid redundant computation.

Let's take a look at an example of using the top-down approach to calculate the Fibonacci sequence:

1#include <iostream>
2#include <vector>
3
4int fib(int n, std::vector<int>& memo) {
5    if (n <= 1) {
6        return n;
7    }
8
9    if (memo[n] != -1) {
10        return memo[n];
11    }
12
13    int result = fib(n-1, memo) + fib(n-2, memo);
14    memo[n] = result;
15    return result;
16}
17
18int main() {
19    int n = 10;
20    std::vector<int> memo(n + 1, -1);
21    int result = fib(n, memo);
22    std::cout << "The Fibonacci number at position " << n << " is " << result << std::endl;
23    return 0;
24}

xxxxxxxxxx

#include <iostream>

#include <vector>

​

int fib(int n, std::vector<int>& memo) {

    if (n <= 1) {

        return n;

    }

​

    if (memo[n] != -1) {

        return memo[n];

    }

​

    int result = fib(n-1, memo) + fib(n-2, memo);

    memo[n] = result;

    return result;

}

​

int main() {

    int n = 10;

    std::vector<int> memo(n + 1, -1);

    int result = fib(n, memo);

    std::cout << "The Fibonacci number at position " << n << " is " << result << std::endl;

    return 0;

}