What is Bottom-up Approach in C++

A bottom-up approach in programming refers to a problem-solving strategy where you start by solving smaller subproblems and gradually build up to solve the larger problem. In contrast to a top-down approach, where you start by solving the larger problem and break it down into smaller subproblems, the bottom-up approach focuses on solving the simplest cases first and then combining their solutions to solve more complex cases.

The bottom-up approach is often associated with dynamic programming and iterative methods. It’s particularly useful when solving problems that exhibit optimal substructure and overlapping subproblems. This approach can lead to efficient and optimized solutions, as it avoids redundant calculations by reusing solutions to previously solved subproblems.

Here’s a general outline of the bottom-up approach:

1. Start with Base Cases: Identify the simplest and smallest cases of the problem that can be solved directly. These serve as the base cases for building up the solution.
2. Solve Smaller Subproblems: Solve the subproblems that are slightly larger and more complex than the base cases. Use their solutions to solve larger subproblems.
3. Combine Solutions: Combine the solutions of the smaller subproblems to solve larger subproblems. Reuse the solutions whenever possible to avoid redundant calculations.
4. Build Up to the Original Problem: Continue this process of solving and combining solutions until you have solved the original problem.
5. Optimize and Store Solutions: In dynamic programming, the bottom-up approach often involves storing solutions to subproblems in a table (e.g., an array or a matrix) to avoid recalculating them.

Here’s a simple example using the bottom-up approach to calculate the nth Fibonacci number:

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) {
        return n;  // Base cases
    }

    int dp[n + 1];  // Table to store solutions to subproblems
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];  // Combine solutions
    }

    return dp[n];  // Solution to the original problem
}

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

In this example, the bottom-up approach builds up the solution to the Fibonacci sequence by solving and combining solutions for smaller subproblems, storing them in the dp array. This approach ensures that each subproblem is solved only once, leading to improved efficiency compared to a naive recursive solution.