Bottom-up Approach

The bottom-up approach, also known as the iterative approach, is another common approach in dynamic programming. It involves solving the problem by starting with the base cases and iteratively building up the solutions to larger subproblems.

In the bottom-up approach, we use a table or an array to store the solutions to the subproblems. We start with the base cases and compute the solutions for smaller subproblems, gradually moving towards the final solution.

One of the advantages of the bottom-up approach is that it avoids the overhead of recursive function calls, making it more efficient in some cases. It is particularly useful when the dependencies between subproblems are well-defined and can be computed in a straightforward manner.

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

1#include <iostream>
2#include <vector>
3
4int bottomUpFibonacci(int n) {
5    std::vector<int> dp(n + 1);
6    dp[0] = 0;
7    dp[1] = 1;
8
9    for (int i = 2; i <= n; i++) {
10        dp[i] = dp[i - 1] + dp[i - 2];
11    }
12
13    return dp[n];
14}
15
16int main() {
17    int n = 10;
18    int result = bottomUpFibonacci(n);
19    std::cout << "The Fibonacci number at position " << n << " is " << result << std::endl;
20    return 0;

xxxxxxxxxx

#include <iostream>

#include <vector>

​

int bottomUpFibonacci(int n) {

    std::vector<int> dp(n + 1);

    dp[0] = 0;

    dp[1] = 1;

​

    for (int i = 2; i <= n; i++) {

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

    }

​

    return dp[n];

}

​

int main() {

    int n = 10;

    int result = bottomUpFibonacci(n);

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

    return 0;

}