The Magic of Dynamic Programming: Solving Programming Challenges with Ease

Welcome back to the Hackerrank Interview Preparation Kit! In this series, I usually solve algorithmic programming problems and narrate my thought process. However, today’s video is different. I want to teach you an important technique called dynamic programming (DP). Trust me, this technique is a game-changer.

Dynamic programming is a super important technique that frequently appears in programming challenges. It can also be useful in your day-to-day programming. While you might not need to use dynamic programming every day, when it is necessary, it’s incredibly beneficial to have this technique in your arsenal. Many existing algorithms, such as shortest path algorithms, employ dynamic programming approaches. By understanding these techniques, you’ll be able to create your own novel algorithms that have the same power and energy.

Let’s delve into the dynamic programming section and solve a problem together. The problem is relatively straightforward: given an array of integers, we need to find the subset of non-adjacent elements with the maximum sum. In other words, we want to select a subset of elements from the array that maximizes the sum, with the constraint that no two selected elements can be adjacent.

It might sound simple, but finding the optimal solution isn’t as easy as it seems. Brute force enumeration of all possible subsets and calculating their sums would be time-consuming and inefficient, especially for larger arrays. A greedy approach, where we always select the largest available element, also won’t work for all cases.

So how do we solve this problem efficiently? This is where dynamic programming comes in. Dynamic programming is closely related to recursion, particularly recursion seen in mathematical proofs by induction. By formulating the problem recursively, we can solve it more effectively.

Let’s define a function, f(n), where n represents the size of the array. The goal is to find the maximum sum for a given subset of the array. To achieve this, we’ll make a leap of faith and assume that the solution for f(n-1) already exists. We want to determine if we can calculate f(n) by using the solution for f(n-1) and including an additional value.

To do this, we’ll consider two options: taking the additional value or leaving it. If we take the value, we must exclude the adjacent element, so the answer would be f(n-2). If we leave the value, the answer would be f(n-1). We’ll select the option that gives us the maximum result, which gives us our recursive function f(n).

Now, if we try to solve for f(5), we’ll make two function calls: f(3) and f(4). f(3) will further call f(1), and f(4) will call f(2). However, when f(1) and f(2) are called, they will encounter a termination point as they require solving f(-1) and f(0), which aren’t valid. These termination points indicate that we need special cases for f(1) and f(2).

So, to summarize, our recursive formulation is as follows:

• If n is equal to 1, return the maximum of the first element in the array and 0.
• If n is equal to 2, return the maximum of the first two elements in the array.

Now we can code up our recursive function and the table to store the results. Instead of using a top-down approach, we’ll use a bottom-up approach, starting from the base cases and building up the subsequent values of f(n) by referring to the previously calculated values. This way, we avoid redundant computations and dramatically reduce the time complexity.

Let’s see the code in action:

#include <iostream>
#include <vector>
#include <algorithm>

int maxSubsetSum(std::vector<int> arr) {
    if (arr.size() == 1) {
        return std::max(arr.front(), 0);
    } else if (arr.size() == 2) {
        return std::max(arr[0], arr[1]);
    }

    std::vector<int> table(arr.size());
    table[0] = std::max(arr[0], 0);
    table[1] = std::max(arr[0], arr[1]);

    for (int i = 2; i < arr.size(); i++) {
        table[i] = std::max(arr[i] + table[i - 2], table[i - 1]);
    }

    return table.back();
}

int main() {
    std::vector<int> arr = {3, 7, 4, 6, 5};
    std::cout << maxSubsetSum(arr) << std::endl;

    return 0;
}

When we run the code, we obtain the expected result of 13. This approach works efficiently for larger arrays as well.

Dynamic programming is a powerful technique that can significantly improve the efficiency of solving programming challenges. It involves breaking down a problem into smaller subproblems and storing the results to avoid redundant computations. By formulating the problem recursively and building up the solutions from the bottom, we can achieve optimal solutions with reduced time complexity.

So, the next time you encounter a challenging programming problem, consider using dynamic programming techniques. With a bit of practice, you’ll become a master at solving even the most complex problems efficiently. Happy coding!

References:

• Techal