LeetCode 265, 1937, 887 and 1703.
Dynamic programming is one of the most common algorithmic paradigms in coding interview questions. Typically, it takes two steps to solve a dynamic programming problem: (1) spot the recurrence structure of the problem and formulate the state transition function; (2) devise an efficient way to compute the values — as well as the optimal actions — of the states.
In this post, I will introduce you to four LeetCode problems where it takes a bit of ingenuity to compute the values/actions in a time-efficient way, although the state transitions are pretty straightforward.
LC 265 Paint House II
In this question, you are asked to minimize the cost of painting a row of n houses using k colors, such that no two adjacent houses have the same color. The cost of painting each house with each color is given by a matrix costs, where costs[i][j] is the cost of painting house i (0≤i<n) with color j (0≤j<k).
Let’s denote dp(i, j) as the minimum cost for painting the first (i+1) houses such that house i is painted in color j. Then it’s easy to formulate the state transition:
If we iteratively compute the values as the formula suggests, it would take O(n * k²) time to get the final answer dp(n-1, k-1). Instead, one should note that repeatedly calculating the optimal precursor value dp(i-1, j’) is probably a waste of time. Typically for any j, the best j’ should be chosen as the one that minimizes dp(i-1, j’), provided that either of the two conditions hold: (1) there exist more than one j’ that minimizes dp(i-1, j’) so that we can always choose a color different from that of the current house; (2) dp(i, j) is not the minimum value among dp(i, j’)s for all j’. Only when both of the conditions fail do we need to use the second best precursor state for the current color. So for each i>0, we could preprocess the precursor states dp(i-1,*) to find the minimum precursor value, the number of precursor states that lead to the minimum value, and the second minimum precursor value. By doing so, the overall time complexity could be brought down to O(n * k).
LC 1937 Maximum Number of Points with Cost
Given an m x n matrix points, select a column in each row to minimize the accumulated points with cost. The accumulated points with cost is the total sum of the selected numbers in points minus the accumulated cost of switching columns between adjacent rows, where the switching cost from column j in row i to column j’ in row i+1 is |j - j’|.
The technique for this question is pretty similar to that for the last one. Let’s define dp(i, j) as the maximum accumulated points with cost in the first (i+1) rows such that the column j is selected for row i. It’s easy to find the following state transition relation:
As in the last question, a naive implementation would result in an O(m * n²) runtime, which is unacceptable given the input ranges. So how can we do better? For each state (i, j), we can divide the precursor states into (1) those with j’≤j and (2) those with j’≥j, optimize them separately and take the best of the two. Notice that we allow the two groups to overlap at j’=j for sake of simplicity. For j’≤j, we need to choose a different optimal j’ at j+1 from the one we chose at j only if j is a strictly better precursor index, because for all j’<j, the relative optimality between any two precursors stays the same for j and j+1. Thus it takes a constant time to update the precursor state at j+1 when we already know the precursor state j, and the same reasoning applies to the situation where j’≥j. So it takes O(n) to calculate values in each row, and the total time complexity is O(m * n).
LC 887 Super Egg Drop
There is a building of n floors numbered from 0 to n-1, and there exists some f (0≤f≤n) such that an egg dropped from a floor lower than f will stay intact but an egg dropped from a floor higher than or equal to f will break. Given that there are k (k>0) eggs, calculate the minimum number of drops one needs to make to determine the value of f?
Notice that in such questions we need to consider the worst situation we could meet when following a specific policy, just like how we consider the optimal opponent moves in the minimax algorithm. If we have only one egg left, the best thing to do is try floor from 0 to n-1 until we find the first floor where the egg breaks after being dropped from there. But if we have more than one egg, we could judiciously select a floor p to make the first attempt and then take subsequent actions depending on whether the first egg breaks or not. If the first egg breaks, then we recursively look at floors lower than p, otherwise we look at floors higher than p. Define dp(i, j) as the minimum number of drops for i floors using j eggs, then we have:
The most naive implementation takes O(n² * k) time, which is far from acceptable. With a bit of thought, you might notice that as p increases, dp(p, j-1) will ramp up while dp(i-p-1, j) will decline. So for each i and j, we could do a binary search to determine the point where dp(p, j-1) surpasses dp(i-p-1, j), and that should be the point where the maximum of the two reaches the minimum. Thus the time complexity could be reduced to O(n * log n * k), which could pass LeetCode tests.
Nevertheless, we could do even better than that. Remember in LC 240 Search a 2D Matrix II, we don’t just do a binary search in each row, but instead we exploit the relations between adjacent rows and update the frontier incrementally. We could use the same technique here. Notice that for the same j, when switching from i to i+1, the p value representing the first position where dp(p, j-1) surpasses dp(i-p-1, j) will only increase. That’s because dp(p, j-1) will stay the same, while dp(i-p-1, j) will increase as i increments. So as shown in the plot given by the LeetCode official solution, the downwards curve on the left is raised as the upwards curve on the right stays the same, causing the intersection moves along the latter curve to the right. Hence, we could incrementally update the p value in one direction as i increases. The overall time complexity is O(n * k).
LC 1703 Minimum Adjacent Swaps for K Consecutive Ones
Given a list of n digits, either zero or one, determine the minimum number of swaps one needs to make in order to create k consecutive ones. Each time, a swap needs to be made on two adjacent digits.
Actually, this is not a dynamic programming question, but I want to include it here because it employs the same idea of incremental update as in the last question. Imagine there is a sliding window that encompasses exactly k ones in the original sequence as we proceeds from left to right. Each time we calculate the number of adjacent swaps it takes to group together all the ones in the window, and the final answer is the minimum value among all the windows.
Now let’s look at one sliding window. Suppose the original indices of the ones are given by an array A of size k. Leveraging a bit of middle school maths, we could conclude that the most efficient way to group them together is to fix the one at A[(k-1)/2] (the median position) and move the rest towards it from both sides. And to calculate the minimum number of swaps, we don’t need to simulate the swaps or track the swaps for putting each one in place. Instead, we could first calculate the total swaps to move all the ones to the same median position, and then subtract the result by the number of swaps it takes to spread them out from the median position.
That is great, but calculating this for each sliding window could result in O(n * k) overall runtime. Is it possible to quickly determine the answer of the next window given the answer of the previous window? The answer is affirmative. As the sliding window moves one step ahead, the median position will change from A[(k-1)/2] to A[(k+1)/2]. Let’s denote d as the distance from the old median position to the new median position. Except for the leftmost one in the old window and the rightmost one in the new window, the rest of the k-1 ones will adapt to this change in two ways: (1) those to the left of the new median will need d more swaps; (2) those to the right of the old median will take d fewer swaps. Thus, except for the first window that needs O(k) time to calculate, all the subsequent windows just need constant times for incremental updates. In total, we need O(n+k) time to obtain the final answer.
Thanks for reading this! If you find this helpful, please give me a clap and stay tuned for my future posts.
