Deliberate practice techniques for software developers
LeetCode 416: Partition Equal Subset Sum gives us another chance to practice multidimensional dynamic programming. The problem asks:
Given an integer array
nums, returntrueif you can partition the array into two subsets A and B such that the sum of the elements in A equals the sum of the elements in B. Returnfalseif this is not possible.
LeetCode 1143: Longest Common Subsequence asks:
Given two strings, return the length of their longest common subsequence.
As we saw when solving the Longest Increasing Subsequence problem, a subsequence is formed by selecting elements from the input, with the only restriction being that they remain in their original order. For the LCS problem, if our two input strings are text1 and text2, we can make a common subsequence using these steps: Iterate through text1 in order. For each character, either select it or don’t select it. When we get to the end of text1, we’ll have a subsequence made up of characters from text1. Then iterate through text2 and look for those same characters, in the same order. If we can find them all, we have found a common subsequence. We need to find the longest such subsequence.
As we have seen in previous weeks, a key step in analyzing a dynamic programming problem is selecting state variables that identify the subproblems to be solved. The solutions to these subproblems are stored in a table, which allows us to retrieve them efficiently when they come up again. So far, we have looked at problems with only one state variable. But the dynamic programming process also works when more than one state variable is required.
Last week, we looked at a problem involving a subarray. A subarray is a contiguous sequence of elements from an array, meaning we can’t skip any elements when building the answer. A subsequence, on the other hand, allows us to skip elements, though the elements in the subsequence still need to stay in their original order.
LeetCode 300: Longest Increasing Subsequence says:
Given an integer array
nums, return the length of the longest strictly increasing subsequence.
So we’re allowed to skip elements, but we can’t change the order of the elements, and for this problem, the elements in the solution must be strictly increasing.
The maximum subarray problem is famous enough to have its own Wikipedia page, and a named algorithm you can use to solve it (Kadane’s Algorithm). But rather than looking up the algorithm, we’ll derive the solution to LeetCode 53: Maximum Subarray using principles of dynamic programming.
The problem statement is simple. Here’s the LeetCode version:
Given an integer array
nums, find the subarray with the largest sum, and return its sum.
A subarray is a contiguous and non-empty sequence of elements from the input array. So we’re looking for the largest sum of all values from nums[i] to nums[j] (inclusive), where i <= j.
Using what we have covered so far, you can analyze a dynamic programming problem and solve it using DP techniques and concepts. But after solving a few problems, you might still feel like you have to invent a new solution each time. In the introduction to this year’s project, I promised to explain a process for designing Dynamic Programming algorithms. This week, I’ll fill in a few details that make solving DP problems more of a repeatable process.
Last week, we looked at a dynamic programming problem for the Jump Game problem. If you implement that solution and run it on LeetCode, you’ll notice that your runtime and memory scores are very low compared to other users. Let’s see why that is.
Let’s solve LeetCode problem 55 (Jump Game) using dynamic programming. Next week, we’ll consider a sneaky aspect of this problem.
The problem:
You are playing a game on a number line where the aim is to reach position n-1 starting from position 0. As input, you get an array nums of size n containing non-negative integers. From position i, you can move forward any distance between 0 and nums[i] (inclusive). Can you reach the last position to win the game?
To solve a problem using dynamic programming, you have to break it into subproblems, solve those subproblems, and use the results to solve the original problem. So the first step in solving a dynamic programming problem is defining what subproblems you need to solve.
To see how the elements of dynamic programming come together in a real problem, let’s explore the classic dynamic programming problem Coin Change (LeetCode 322).