DP — Decision Problem using Memoization

The three most common types of DP problems are - 1. decision problem, 2. combinatorics problem, and 3. optimization problem. We’ll cover all these types of problems in the upcoming blogs. For now, let’s dive into the topic for the day: solving decision problems using DP.

What is a decision problem?

A decision problem is a problem that can be posed as a yes or no question. For example, to assess whether the given number is an even number or not? The answer to the question can be only either yes or no.

Yoda summed it up the best

Now, let’s take an example of a decision problem and try to solve it. Here is the problem, given an array of numbers we have to say whether the given target sum is possible to achieve or not using the numbers present in the array. Given that,

1. the same number may be chosen from the array any number of times
2. the target sum and numbers in the array are all positive integers.

Well, if you think for a while, you can come up with a basic brute recursive solution:

1. We can take a number from the array and subtract it from the target sum. Now, we recursively call the function with the new target sum.
2. The base case can be made to check for whether the target sum is equal to zero or less than zero.
3. If the sum has become negative we return false or if it is equal to 0 we return true.

Basic brute recursive solution

Well, this solution just works fine for this particular test case we have taken but there is an underlying problem in it. The time complexity of the algorithm is O(nᵐ), where n is the size of the array and m is the target sum.

recursion tree of the test case in the code

As you could see in the recursion tree, the tree can almost branch n different ways for each recursive call and the depth can go up to m levels deep (when there is 1 present in the numbers array). Well, this is a brute force algorithm and proves to be of no use. When the size of the array or the target sum grows larger, the time complexity grows exponentially.

Note

This is a continuation of my previous blogs on DP, so if you’re new to DP or need a check on some basic terminologies/concepts, check out my blog over here or any other resources, as in the upcoming paragraphs I will be using some terms related to DP.

DP — Introduction to Dynamic Programming: Part 1

But by taking the brute force approach, we have come to an observation of the underlying DP’s characteristics in this problem. Which are the optimal substructure property and overlapping subproblems. You could notice the overlapping subproblems property from the recursion tree given below:

overlapping subproblems

The optimal substructure property is kind of obvious from the brute algorithm, where we subtract the original target sum with a number from the array and ask the original question but with a new target sum.

So, as we’re familiar with these kinds of cases, our mind reverts to the obvious solution, which is “Let’s memoize the code!”

The general trick here on what part of the code to memoize lies in our return statements. As we saw in our brute algorithm the intermediatory results are the ones that we need to cache in order to cut down the repeated calls to recursive functions with the same question (question in the sense, the parameters - over here it is the target sum).

And we add another base case condition to check whether the target sum is present in the memo object(can be a hashmap, array, dictionary based on your language preference). If it is present in the memo object, we return the result for the particular target sum which was stored as a key-value pair in the memo object.

Memoized solution

Now the code is fairly efficient for real-world applications, as the time complexity is O(m*n). I would like for you all, to try to sketch out the recursion tree for the memoized code, to understand how memoization helps in the huge cut down in time complexity of the algorithm.

Quick Recap

1. We saw about ‘What is a decision problem?’ and an example problem to go with it.
2. We laid out a brute force algorithm to solve the problem.
3. We observed the characteristics of DP in our brute force algorithm.
4. Then we memoized the code, to make the brute force algorithm much more efficient.

What’s next?

I would like you all to try out the combinatorics version of the same problem — how sum? Where you would have to return all the possible combinations of the solutions to the problem. You could check the same problem over in leetcode:

https://leetcode.com/problems/combination-sum/

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in my next post with a combinatorics problem and how to solve the same using DP.

References

1. https://www.youtube.com/watch?v=oBt53YbR9Kk&t=5596s