Dynamic programming in C++

Dynamic programming is a powerful technique for solving complex problems by breaking them into smaller overlapping subproblems. It works well when we can construct the solution to a larger problem from the solutions of its subproblems.

In this Answer, we will explore the basics of dynamic programming, the approaches used, and examples of its implementation in C++.

Steps for solving problems using dynamic programming

The following steps outline a typical approach to solving problems using dynamic programming:

Steps for solving problems using dynamic programming
Steps for solving problems using dynamic programming

  1. Break the problem: Divide the complex problem into smaller subproblems that can be solved independently.

  2. Define the recurrence relation: The recurrence relation defines the solution to a problem by expressing it in terms of solutions to its subproblems through a recursive formula.

  3. Create a memoization table: To avoid redundant computations, create a memoization table as a data structure to store the results of subproblems.

  4. Fill the table iteratively: Use an iterative loop or recursion with memoizationMemoization is a technique used in dynamic programming to store and reuse the results of expensive function calls to avoid redundant computations. to compute and store the results of the subproblems in the table.

  5. Compute the final solution: The final solution to the original problem is computed by retrieving the solution from the memoization table.

Understanding dynamic programming

Let's understand dynamic programming using the example of finding the nth Fibonacci number. We'll start with the recursive solution and then demonstrate how the dynamic programming approach improves its efficiency.

Recursive solution

The Fibonacci sequence is defined as follows:

and for n > 1:

int fibonacci_seq(int number) {
    if (number <= 1)
        return number;
    
    return fibonacci_seq(number - 1) + fibonacci_seq(number - 2);
}

The time complexity of the recursive solution is O(2n). This is because the recursive solution makes redundant function calls and calculates the same Fibonacci numbers multiple times. This leads to an exponential growth in the number of function calls and computations.

Dynamic programming solution

To improve the efficiency of the Fibonacci calculation, we utilize dynamic programming techniques.

int fibonacci_seq(int number) {
    std::vector<int> table(number + 1);
    table[0] = 0;
    table[1] = 1;
    
    for (int i = 2; i <= number; i++) {
        table[i] = table[i - 1] + table[i - 2];
    }
    
    return table[number];
}

In the dynamic programming solution, we create a table table to store the results of previously computed Fibonacci numbers. We start with the base cases (table[0] = 0 and table[1] = 1). Then, we iteratively fill the table from index 2 to n, calculating each Fibonacci number by summing the previous two Fibonacci numbers. By avoiding redundant calculations and storing the results in the table, we can directly access and reuse the values when needed.

Hence, the time complexity for this solution is O(n).

Approaches for dynamic programming

There are two approaches used for dynamic programming:

  • Top-down approach

  • Bottom-up approach

Approaches for dynamic programming
Approaches for dynamic programming

Top-down approach

The top-down approach in dynamic programming starts with the original problem and recursively breaks it into smaller subproblems. It uses memoization to store the results of previously computed subproblems to avoid redundant computations. The top-down approach can be implemented using recursion or memoization techniques.

Code example

Below is the code to calculate the Fibonacci sequence using the top-down approach:

#include <iostream>
#include <vector>
using namespace std;
vector<int> dp;
int fibonacciTopDown(int input_num) {
    if (input_num <= 1)
        return input_num;
  
    if (dp[input_num] != 0)
        return dp[input_num];
    return dp[input_num] = fibonacciTopDown(input_num - 1) + fibonacciTopDown(input_num - 2);
}
int main() {
    int number = 12; // Compute the 12th Fibonacci number
    dp.resize(number + 1, 0); // Initialize memoization table
    int result = fibonacciTopDown(number);
    cout << "The " << number << "th Fibonacci number is: " << result << endl;
    return 0;
}

Code explanation

Here's a line-by-line explanation for the above code:

  • Lines 1–2: The necessary header files are included. iostream provides input/output streams, and vector allows the use of dynamic arrays.

  • Line 4: The using directive is used to avoid writing std:: before standard library elements.

  • Line 6: dp is a vector that will be used for memoization, storing already computed Fibonacci numbers.

  • Lines 8–16: The fibonacciTopDown function is a recursive function. It takes an integer input_num as input and returns the corresponding Fibonacci number.

    • If the input number is 0 or 1, the function returns the number itself since the Fibonacci of 0 and 1 is the number itself.

    • If the Fibonacci number for input_num has already been computed and stored in the dp vector, it is directly returned.

    • Otherwise, the function recursively calls itself to calculate the Fibonacci number for input_num-1 and input_num-2, and adds them together. The result is stored in dp[input_num] for future use and returned.

  • Lines 18–28: The main function is the entry point of the program.

    • The input_num is set to 12, indicating that we want to compute the 12th Fibonacci number.

    • The dp vector is resized to input_num + 1 elements and initialized to 0. This creates a memoization table where we can store already computed Fibonacci numbers.

    • result is assigned the value of fibonacciTopDown(input_num).

    • Finally, the result is printed to the console using cout.

Bottom-up approach

The bottom-up approach in dynamic programming starts by solving the smallest subproblems and gradually builds the solution to larger subproblems. It is an iterative approach where the solutions to subproblems are computed and stored in a table or array. The final solution is obtained by combining the solutions to the subproblems.

Code example

Below is the code to calculate the Fibonacci sequence using the bottom-up approach:

#include <iostream>
#include <vector>
using namespace std;
int fibonacciBottomUp(int input_num) {
    if (input_num <= 1)
        return input_num;
    vector<int> dp(input_num + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= input_num; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[input_num];
}
int main() {
    int number = 12; // Compute the 12th Fibonacci number
    int result = fibonacciBottomUp(number);
    cout << "The " << number << "th Fibonacci number is: " << result << endl;
    return 0;
}

Code explanation

Here's a line-by-line explanation for the above code:

  • Lines 1–2: The necessary header files are included. iostream provides input/output streams, and vector allows the use of dynamic arrays.

  • Line 4: The using directive is used to avoid writing std:: before standard library elements.

  • Lines 6–18: The fibonacciBottomUp function calculates the Fibonacci number using the bottom-up approach (tabulation).

    • If the input number is 0 or 1, the function returns the number itself since the Fibonacci of 0 and 1 is the number itself.

    • A dp vector is created with input_num + 1 elements and initialized to 0. This vector will store the Fibonacci numbers.

    • The base case dp[1] = 1 is set, representing the Fibonacci of 1.

    • A loop is used to iterate from 2 to input_num, filling in the dp vector adding the previous two Fibonacci numbers.

    • At each iteration, dp[i] is calculated by adding dp[i-1] and dp[i-2].

    • Finally, the function returns dp[input_num], which represents the Fibonacci number for the given input input_num.

  • Lines 20–28: The main function is the entry point of the program.

    • input_num is set to 12, indicating that we want to compute the 12th Fibonacci number.

    • result is assigned the value of fibonacciBottomUp(input_num).

    • Finally, the result is printed to the console using cout.

Conclusion

The bottom-up and top-down approaches in dynamic programming provide efficient solutions to complex problems. By breaking down problems into smaller subproblems and reusing their solutions, dynamic programming reduces redundant computations and improves efficiency. These approaches are powerful tools for solving a wide range of problems and optimizing time complexity.

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved