DP — Optimization Problem using Tabulation

In the previous blogs, we have seen how to solve the decision and combinatorics problems using DP — tabulation. This time, we’ll see about solving an optimization problem using DP — tabulation.

What is an optimization problem?

In mathematics and computer science, an optimization problem is a problem of finding the best solution from all feasible solutions. For example, what is the best way to obtain the sum 10 by using the array of elements consisting of {1, 2, 5}? The answer to that is {5, 5} as it is the best solution available among other solutions like for example {2,2,2,2,2} or {2,2,1, 5} and etc.,

Now, let’s take an example of an optimization problem and try solving it.

Note

If you’re new to DP or need a quick check on some basic terminologies concepts, especially on tabulation, check out my blog over here or any other resources, as moving on with the concepts requires some familiarity with the basics of DP.

DP — Introduction to Dynamic Programming: Part 2

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array houses representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police

Intuition

The straightforward approach to this problem will be of brute-force, where we have to make two choices:

a. Don’t rob the house and move to the next house.

b. Rob the house and move to the house after the next house.

So, we will be trying out combinations of these choices and find the one which gives us the maximum amount of money.

brute force

But this approach isn’t feasible for real-world problems as this has a time complexity of O(2ⁿ), where n is the number of houses present to us, and for each house, we have 2 choices to make whether to rob the house or not, so we end up this exponential time complexity.

recursion tree

But from this recursive algorithm, we can observe the overlapping subproblems and optimal substructure of this problem. So the idea is that if recursive calls with the same arguments are repeatedly made, the inefficient recursive algorithm can be tabulated by caching these results of the subproblems so that we don’t have to recompute it.

Here, we use an array called dp to save the results of computation. In this case, dp[i] will denote the maximum money that we can get by considering ith house. At every house, we have a decision to make among the following choices:

i. Skip the current house, i.e., we can keep the same money as we had at the previous index = dp[i-1]

ii. Or, we can rob the current house and add it to the money we had at i-2th index - houses[i] + dp[i-2]

Algorithm

1. If the number of houses is equal to one, the answer is obviously the money stashed in the house, so return it.
2. Else if the number of houses is equal to two, the answer is the maximum of the money stashed in both of the houses.
3. Else, follow the steps given below:

a. Create an array of size n, called dp which will store the results of the subproblems.

b. As we iterate through the houses array, for each index we do the following computation:

dp[idx] = max(dp[idx-1], houses[idx] + dp[idx-2])

4. Return the result stored in dp[n — 1] which will be the maximum amount that can be robbed.

Code

house robber — optimal solution using tabulation

The time complexity of the above code is O(n), where n is the number of houses.

What’s next?

You can try this same problem on leetcode in a space-efficient manner, and try the expansion problems of the same:

House Robber - LeetCode

House Robber II - LeetCode

House Robber III - LeetCode

General Note on Dynamic Programming

1. Identify the overlapping subproblems.
2. Identify what may be the trivially smallest input.
3. Either think recursively to use memorization or think iteratively to use tabulation.
4. Work through the strategy first and then code the solution!

So, we have come to the end of this post and the dynamic programming series, and thank you so much 😊 if you have made it this far into this post and the series. I will see you in my next post.

References

1. https://www.youtube.com/watch?v=oBt53YbR9Kk
2. https://leetcode.com/problems/house-robber/discuss/1605797/C%2B%2BPython-4-Simple-Solutions-w-Explanation-or-Optimization-from-Brute-Force-to-DP