DSA for Interviews, From Zero

Part 14 · Lesson 55 · read

1-D Dynamic Programming

House robber, coin change, decode ways, word break and the longest increasing subsequence.

On this page

  1. Defining the state in words
  2. House robber
  3. House robber II: a circle
  4. Coin change
  5. Traced: coin change
  6. Decode ways
  7. Word break
  8. Longest increasing subsequence
  9. Practice questions (7)
  10. Make it stick
  11. What's next

Defining the state in words

In lesson 54 you made slow recursion fast by remembering answers. Now we turn that into a habit. Dynamic programming (DP) is a method that solves a big problem by splitting it into smaller problems that repeat, solving each small problem only once, and saving its answer. Memoization (also called a memo) means saving the answer of a function call, so the next call with the same input just reads it. Think of writing a result in a notebook instead of calculating it again. The most important sentence in any DP solution is the one that starts “dp[i] means …”. This sentence defines the state. The state is the small question whose answer you save for each value of i. When the state is clear, three more things follow almost by themselves:

  1. Base case: the answer for the smallest inputs. You know it without thinking (for example dp[0]).
  2. Transition: a formula that gives dp[i] from answers you already have. To find it, ask “what was the last decision?”
  3. Order: fill the array so that every answer is ready before you use it (usually from left to right).

1-D DP means the state needs only one index, so the table is a single array. Say the sentence out loud before you write any code. This is the best habit in this whole chapter. If you cannot finish the sentence, you do not have a solution yet.

House robber

A row of houses holds nums[i] money each. You may not rob two houses that are next to each other. What is the most money you can take? For every house the last decision is simple: skip it or rob it. If you rob house i, you cannot rob house i + 1, so you continue from i + 2. Here is the state, looking forward:

JavaScript
// State: best(i) = the most money you can take from houses i, i+1, ... to the end.function rob(nums) {  const memo = new Map();  function best(i) {    if (i >= nums.length) return 0;         // no houses left    if (memo.has(i)) return memo.get(i);    const skip = best(i + 1);               // leave house i alone    const take = nums[i] + best(i + 2);     // rob it, so house i+1 is off limits    const result = Math.max(skip, take);    memo.set(i, result);    return result;  }  return best(0);}console.log(rob([1, 2, 3, 1]));    // 4console.log(rob([2, 7, 9, 3, 1])); // 12

Without the memo, this recursion calls itself twice per house, so the time is O(2n). With the memo, each best(i) is worked out only once. The time and space are O(n). You can also state the same problem looking backward. That gives a loop with no recursion at all. This is called tabulation: filling a table (an array) from the smallest answers up to the biggest one. In one line: memoization is top-down (start from the big question and save answers as you go), and tabulation is bottom-up (start from the small answers and build up).

JavaScript
// State: dp[i] = the most money you can take from the FIRST i houses.function rob(nums) {  const n = nums.length;  const dp = new Array(n + 1).fill(0);      // dp[0] = 0: no houses, no money  dp[1] = nums[0];  for (let i = 2; i <= n; i++) {    dp[i] = Math.max(dp[i - 1],             // skip house i (it is nums[i - 1])                     dp[i - 2] + nums[i - 1]); // rob it  }  return dp[n];}console.log(rob([2, 7, 9, 3, 1])); // 12
Dry run · nums = [2, 7, 9, 3, 1]
ihouse iskip: dp[i-1]rob: dp[i-2] + moneydp[i]
0---0
1200 + 2 = 22
2720 + 7 = 77
3972 + 9 = 1111
43117 + 3 = 1011
511111 + 1 = 1212

Each row takes the larger of the two choices. The answer 12 is 2 + 9 + 1.

Notice that each row only looks at the two rows before it. When a table is used like this, you can throw the rest away and keep just two variables. This cuts the space from O(n) to O(1):

JavaScript
// dp[i] only reads dp[i - 1] and dp[i - 2], so two variables are enough.function rob(nums) {  let twoBack = 0;                          // dp[i - 2]  let oneBack = 0;                          // dp[i - 1]  for (const money of nums) {    const current = Math.max(oneBack, twoBack + money);    twoBack = oneBack;    oneBack = current;  }  return oneBack;}console.log(rob([2, 7, 9, 3, 1])); // 12console.log(rob([5]));             // 5

House robber II: a circle

Now the houses stand in a circle. The first and the last house are neighbours, so you cannot rob both. Do not invent a new formula. Instead, split the problem into two problems with a straight row. Any valid plan skips the first house or skips the last one. Solve both rows and take the better answer.

JavaScript
function robLine(nums, lo, hi) {            // the line version, restricted to nums[lo..hi]  let twoBack = 0, oneBack = 0;  for (let i = lo; i <= hi; i++) {    const current = Math.max(oneBack, twoBack + nums[i]);    twoBack = oneBack;    oneBack = current;  }  return oneBack;}function robCircle(nums) {  if (nums.length === 1) return nums[0];    // the two ranges below would both be empty  const withoutLast = robLine(nums, 0, nums.length - 2);  const withoutFirst = robLine(nums, 1, nums.length - 1);  return Math.max(withoutFirst, withoutLast);}console.log(robCircle([2, 3, 2])); // 3console.log(robCircle([1, 2, 3, 1])); // 4console.log(robCircle([1]));       // 1
One house
With a single house, both ranges are empty and would give 0. Handle nums.length === 1 on its own.

Coin change

You get coin values and a target amount. Find the fewest coins that add up to it. You can use each coin value as many times as you like. If it is impossible, return -1. A greedy method (a method that always takes the best-looking choice right now and never looks back) fails here. Here that means always taking the biggest coin first. For coins 1, 3, 4 and amount 6, the biggest coin first gives 4 + 1 + 1 = 3 coins, but 3 + 3 uses only 2 coins.

State: dp[a] = the fewest coins that make exactly the amount a. The last decision is which coin you used last. If it was coin, the rest is the smaller problem dp[a - coin], plus one. Try every coin and keep the smallest result. For amounts that cannot be made, we store Infinity. This works well because Infinity never wins a “smallest” comparison, and Infinity + 1 is still Infinity. We turn it into -1 only at the very end.

JavaScript
// State: dp[a] = the fewest coins that make exactly the amount a (Infinity if impossible).function coinChange(coins, amount) {  const dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0;                                // zero coins make zero  for (let a = 1; a <= amount; a++) {    for (const coin of coins) {      if (coin <= a && dp[a - coin] + 1 < dp[a]) {        dp[a] = dp[a - coin] + 1;           // use one 'coin', then solve the smaller amount      }    }  }  return dp[amount] === Infinity ? -1 : dp[amount];}console.log(coinChange([1, 3, 4], 6)); // 2   (3 + 3, where greedy would pick 4 + 1 + 1)console.log(coinChange([2], 3));       // -1console.log(coinChange([5], 0));       // 0

Here is the top-down version of the same state. It uses a memo (a saved-answers notebook) instead of a loop:

JavaScript
// The same idea top-down: ask for the smaller amount, remember each answer.function coinChange(coins, amount) {  const memo = new Map();  function fewest(rest) {    if (rest === 0) return 0;    if (rest < 0) return Infinity;          // overshot: this path is impossible    if (memo.has(rest)) return memo.get(rest);    let best = Infinity;    for (const coin of coins) best = Math.min(best, fewest(rest - coin) + 1);    memo.set(rest, best);    return best;  }  const answer = fewest(amount);  return answer === Infinity ? -1 : answer;}console.log(coinChange([1, 3, 4], 6)); // 2console.log(coinChange([2], 3));       // -1

The time is O(amount × number of coins) and the space is O(amount). Both versions are correct, but the table avoids deep recursion for large amounts.

Traced: coin change

step 1 / 21
Set up
dp starts as all Infinity

Infinity means 'no way found yet'. We use it (not -1 or 0) so the check dp[a - coin] + 1 < dp[a] stays correct, because Infinity + 1 is still Infinity.

▶const dp = new Array(amount + 1).fill(Infinity);2dp[0] = 0;3for (let a = 1; a <= amount; a++) {4  for (const coin of coins) {5    if (coin <= a && dp[a - coin] + 1 < dp[a]) {6      dp[a] = dp[a - coin] + 1;7    }8  }9}10return dp[amount] === Infinity ? -1 : dp[amount];
Variables
coins[1, 3, 4]
amount6
dp[Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]
Console
(nothing printed yet)
Step through coins [1, 3, 4] and amount 6. Watch dp[6]. It first becomes 3 with coin 1, then 2 with coin 3, and coin 4 cannot beat that. · interactive

Decode ways

A message of digits is decoded with 1 = A, 2 = B, …, 26 = Z. Count the ways to read a string of digits. State: dp[i] = the number of ways to decode the first i characters. The last letter used either one digit (valid when it is 1 to 9, never 0) or two digits (valid when they make a number from 10 to 26). The two counts add up:

JavaScript
// State: dp[i] = the number of ways to decode the first i characters of s.function numDecodings(s) {  const n = s.length;  const dp = new Array(n + 1).fill(0);  dp[0] = 1;                                // one way to decode nothing: the empty message  for (let i = 1; i <= n; i++) {    if (s[i - 1] !== "0") dp[i] += dp[i - 1];   // last character alone is a letter (1-9)    if (i >= 2) {      const two = Number(s.slice(i - 2, i));      if (two >= 10 && two <= 26) dp[i] += dp[i - 2]; // last two characters form a letter (10-26)    }  }  return dp[n];}console.log(numDecodings("12"));  // 2   (AB, L)console.log(numDecodings("226")); // 3   (BZ, VF, BBF)console.log(numDecodings("06"));  // 0   (a leading zero cannot be decoded)
Dry run · s = "226"
iprefixone digit ok?two digits ok?dp[i]
0(empty)--1
12yes: dp[0] = 1-1
222yes: dp[1] = 122 is a letter: dp[0] = 12
3226yes: dp[2] = 226 is a letter: dp[1] = 13

dp[3] = 3: BZ (2, 26), VF (22, 6) and BBF (2, 2, 6).

Word break

Can the string s be cut into pieces that are all in a dictionary (a list of allowed words)? State: dp[i] = true if the first i characters can be split into dictionary words. The last word is s[j..i) for some cut point j. If the start of the string of length j works, and the slice is a word, then the start of length i works too.

JavaScript
// State: dp[i] = true if the first i characters of s can be split into dictionary words.function wordBreak(s, wordDict) {  const words = new Set(wordDict);          // O(1) membership tests  const dp = new Array(s.length + 1).fill(false);  dp[0] = true;                             // the empty prefix is trivially fine  for (let i = 1; i <= s.length; i++) {    for (let j = 0; j < i; j++) {      if (dp[j] && words.has(s.slice(j, i))) {  // prefix j works, and s[j..i) is a word        dp[i] = true;        break;      }    }  }  return dp[s.length];}console.log(wordBreak("leetcode", ["leet", "code"]));                  // trueconsole.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false

There are O(n²) pairs (j, i), and each slice and lookup costs up to O(n) because it copies and hashes the characters. So the time is about O(n³) in the worst case. The space is O(n). Tip: if the longest dictionary word has length L, try only j values from i - L upwards. That makes it O(n × L).

Longest increasing subsequence

A subsequence keeps items in their original order but may skip some. (A subarray is different: it must be one unbroken piece.) Find the length of the longest strictly increasing subsequence, where every number is bigger than the one before. State: dp[i] = the length of the longest increasing subsequence that ends at nums[i]. Look back at every earlier smaller number nums[j] and add one to its chain. The answer is the biggest value over all i, because the best chain can end anywhere.

JavaScript
// State: dp[i] = the length of the longest increasing subsequence that ENDS at nums[i].function lengthOfLIS(nums) {  const dp = new Array(nums.length).fill(1);   // every element alone is a subsequence of length 1  let best = 0;  for (let i = 0; i < nums.length; i++) {    for (let j = 0; j < i; j++) {      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);  // extend a chain ending at j    }    best = Math.max(best, dp[i]);           // the chain may end anywhere  }  return best;}console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4   (2, 3, 7, 18)console.log(lengthOfLIS([7, 7, 7]));                      // 1   (strictly increasing: equal values do not extend)

The time is O(n²) and the space is O(n). A cleverer method with binary search (a way to find a value in a sorted list by checking the middle and discarding half each time) reaches O(n log n). You will meet it in lesson 57.

The 'ends at' trick
A common move is to define the state as “the best answer ending exactly at i” instead of “the best answer in the first i items”. It forces the choice to connect to the next item. At the end, you take the biggest value overall.

Practice questions

For each question, first write “dp[i] means …”. Then write the base case, the transition and the order. Only then write the code.

Q1House robberMedium

Houses in a row hold nums[i] money each. You cannot rob two houses that are next to each other. Return the most money you can rob.

Example 1
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 0 (1) and house 2 (3): 1 + 3 = 4. They are not next to each other.
Example 2
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob houses 0, 2 and 4: 2 + 9 + 1 = 12.
Stuck? Open one hint at a time
Hint 1
Finish the sentence: “best(i) is the most money from house i to the end.”
Hint 2
For house i you either skip it or rob it. What is left to decide after each choice?
Hint 3
Each answer reads only the two before it. Do you need a whole array?
Show all 3 solutions with explanations
Approach 1Recursion with memo (top-down)
The idea

Define best(i) as the most money from house i to the end. Either skip (best(i + 1)) or rob (nums[i] + best(i + 2)). Save each result in a cache. Without the cache the time is O(2n).

JavaScript
function rob(nums) {  const memo = new Map();  function best(i) {    if (i >= nums.length) return 0;    if (memo.has(i)) return memo.get(i);    const result = Math.max(best(i + 1), nums[i] + best(i + 2));    memo.set(i, result);    return result;  }  return best(0);}console.log(rob([1, 2, 3, 1]));    // 4console.log(rob([2, 7, 9, 3, 1])); // 12
How it works

There are only n different values of i, and each is solved once. So the time and space are O(n). The recursion goes up to n levels deep.

Approach 2Table (bottom-up)
The idea

Let dp[i] be the best total from the first i houses. dp[0] = 0, dp[1] = nums[0], and dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]).

JavaScript
function rob(nums) {  const n = nums.length;  const dp = new Array(n + 1).fill(0);  dp[1] = nums[0];  for (let i = 2; i <= n; i++) {    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);  }  return dp[n];}console.log(rob([1, 2, 3, 1]));    // 4console.log(rob([2, 7, 9, 3, 1])); // 12
How it works

This uses the same formula, filled from left to right with no recursion. The time is O(n) and the space is O(n).

Approach 3Two variables
The idea

Keep only dp[i - 2] and dp[i - 1], in two variables called twoBack and oneBack. Move them forward at each step.

JavaScript
function rob(nums) {  let twoBack = 0, oneBack = 0;  for (const money of nums) {    const current = Math.max(oneBack, twoBack + money);    twoBack = oneBack;    oneBack = current;  }  return oneBack;}console.log(rob([1, 2, 3, 1]));    // 4console.log(rob([2, 7, 9, 3, 1])); // 12
How it works

The time is O(n) and the space is O(1). Step by step on [1,2,3,1]: (0,0), then (0,1), (1,2), (2,4), (4,4). The answer is 4.

Which approach should you use?

Start with the memoised recursion to get the state right. Then change it to the two-variable loop. It is short, fast and uses a fixed amount of space. (LeetCode 198.)

Q2House robber IIMedium

This is the same as house robber, but the houses stand in a circle. The first and last houses are next to each other. Return the most money you can rob.

Example 1
Input: nums = [2,3,2]
Output: 3
Explanation: House 0 and house 2 are neighbours in the circle, so you cannot take both 2s. Take the 3.
Example 2
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 0 (1) and house 2 (3). House 3 is next to house 0, so it is not used.
Stuck? Open one hint at a time
Hint 1
The only new rule is that the first house and the last house are neighbours.
Hint 2
Any valid plan skips the first house, or skips the last house, or skips both.
Hint 3
Run the straight-row version twice, on two ranges, and take the larger answer. Watch out for the case with one house.
Show all 2 solutions with explanations
Approach 1Two line problems
The idea

Take the better of two answers. One is robbing within nums[0..n-2] (last house left out). The other is robbing within nums[1..n-1] (first house left out). Solve each with the house-robber loop.

JavaScript
function robLine(nums, lo, hi) {  let twoBack = 0, oneBack = 0;  for (let i = lo; i <= hi; i++) {    const current = Math.max(oneBack, twoBack + nums[i]);    twoBack = oneBack;    oneBack = current;  }  return oneBack;}function rob(nums) {  if (nums.length === 1) return nums[0];  return Math.max(robLine(nums, 0, nums.length - 2), robLine(nums, 1, nums.length - 1));}console.log(rob([2, 3, 2]));    // 3console.log(rob([1, 2, 3, 1])); // 4console.log(rob([5]));          // 5
How it works

The two ranges together cover every valid plan. A plan that uses the first house cannot use the last house (range 1). Any other plan fits inside range 2. The time is O(n) and the space is O(1).

Approach 2Memo with a flag
The idea

Recurse over (i, tookFirst). If the first house was robbed, the last house is not allowed. This needs twice as many states, but the circle rule is kept inside the state itself.

JavaScript
function rob(nums) {  const n = nums.length;  if (n === 1) return nums[0];  const memo = new Map();  function best(i, tookFirst) {    if (i >= n) return 0;    if (i === n - 1 && tookFirst) return 0;     // the last house touches the first    const key = i * 2 + (tookFirst ? 1 : 0);    if (memo.has(key)) return memo.get(key);    const skip = best(i + 1, tookFirst);    const take = nums[i] + best(i + 2, tookFirst || i === 0);    const result = Math.max(skip, take);    memo.set(key, result);    return result;  }  return best(0, false);}console.log(rob([2, 3, 2]));    // 3console.log(rob([1, 2, 3, 1])); // 4console.log(rob([5]));          // 5
How it works

There are 2n states and each takes O(1), so the time and space are O(n). It is more flexible for other circle problems, but longer than the two-range trick.

Which approach should you use?

Use the two-range trick. Reuse the straight-row problem you already solved instead of inventing something new. Remember this idea: “turn the new problem into one you already solved”. (LeetCode 213.)

Q3Coin changeMedium

You are given coin values (you have as many coins of each value as you want) and a target amount. Return the fewest coins that make exactly that amount. Return -1 if it cannot be made.

Example 1
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 5 + 5 + 1 = 11, which uses three coins.
Example 2
Input: coins = [2], amount = 3
Output: -1
Explanation: You cannot make 3 from coins of 2.
Example 3
Input: coins = [1], amount = 0
Output: 0
Explanation: Zero coins make the amount zero.
Stuck? Open one hint at a time
Hint 1
Greedy (always taking the biggest coin) fails for coins [1,3,4] and amount 6. Can you see why?
Hint 2
State: dp[a] is the fewest coins for exactly the amount a. Which coin was used last?
Hint 3
Use Infinity for “impossible”, and change it to -1 only at the end.
Show all 2 solutions with explanations
Approach 1Recursion with memo
The idea

fewest(rest) tries each coin and recurses on rest - coin. A negative remainder returns Infinity (you went over the amount). Save the results by remainder. Without the cache the time grows exponentially.

JavaScript
function coinChange(coins, amount) {  const memo = new Map();  function fewest(rest) {    if (rest === 0) return 0;    if (rest < 0) return Infinity;    if (memo.has(rest)) return memo.get(rest);    let best = Infinity;    for (const coin of coins) best = Math.min(best, fewest(rest - coin) + 1);    memo.set(rest, best);    return best;  }  const answer = fewest(amount);  return answer === Infinity ? -1 : answer;}console.log(coinChange([1, 2, 5], 11)); // 3console.log(coinChange([2], 3));        // -1console.log(coinChange([1], 0));        // 0
How it works

There are at most amount + 1 different remainders and each one tries every coin. The time is O(amount × coins) and the space is O(amount). For a big amount, the recursion can go thousands of calls deep.

Approach 2Table (bottom-up)
The idea

Fill dp[0..amount] with Infinity, set dp[0] = 0, then for each amount, try every coin that fits.

JavaScript
function coinChange(coins, amount) {  const dp = new Array(amount + 1).fill(Infinity);  dp[0] = 0;  for (let a = 1; a <= amount; a++) {    for (const coin of coins) {      if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);    }  }  return dp[amount] === Infinity ? -1 : dp[amount];}console.log(coinChange([1, 2, 5], 11)); // 3console.log(coinChange([2], 3));        // -1console.log(coinChange([1], 0));        // 0
How it works

This is the same formula, written as a loop. For [1,2,5] the table is 0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3 for amounts 0 to 11. The time is O(amount × coins) and the space is O(amount). Never fill the table with -1, because -1 + 1 = 0 would look like a great answer.

Which approach should you use?

The table is short and has no problem with deep recursion. The memo version is better when only a few amounts are ever reached. (LeetCode 322.)

Q4Decode waysMedium

A message is written as digits with A = 1, B = 2, …, Z = 26. Given a string of digits, return the number of ways to decode it.

Example 1
Input: s = "12"
Output: 2
Explanation: 1|2 is AB, and 12 is L.
Example 2
Input: s = "226"
Output: 3
Explanation: 2|2|6 (BBF), 22|6 (VF) and 2|26 (BZ).
Example 3
Input: s = "06"
Output: 0
Explanation: A zero at the start cannot be decoded. There is no letter for 0 or for 06.
Stuck? Open one hint at a time
Hint 1
State: dp[i] is the number of ways to decode the first i characters.
Hint 2
The last letter came from one digit or from two digits. When is each one allowed?
Hint 3
One digit must not be “0”. Two digits must make a number from 10 to 26.
Show all 2 solutions with explanations
Approach 1Recursion with memo
The idea

ways(i) counts the ways to decode the rest of the string, starting at i. If there is a "0" there, the answer is 0. Otherwise take one digit, and also take two digits if they make a number from 10 to 26.

JavaScript
function numDecodings(s) {  const memo = new Map();  function ways(i) {    if (i === s.length) return 1;               // reached the end: one complete decoding    if (s[i] === "0") return 0;    if (memo.has(i)) return memo.get(i);    let total = ways(i + 1);    if (i + 1 < s.length && Number(s.slice(i, i + 2)) <= 26) total += ways(i + 2);    memo.set(i, total);    return total;  }  return ways(0);}console.log(numDecodings("12"));  // 2console.log(numDecodings("226")); // 3console.log(numDecodings("06"));  // 0
How it works

When we reach the two-digit check, the first digit is not “0”, so the value is at least 10. The time and space are O(n).

Approach 2Table with a rolling pair
The idea

Fill dp[i] from dp[i - 1] (the last digit alone) and dp[i - 2] (the last two digits). Then keep just two variables.

JavaScript
function numDecodings(s) {  let twoBack = 0;   // dp[i - 2], unused until i = 2  let oneBack = 1;   // dp[0] = 1: the empty prefix  for (let i = 1; i <= s.length; i++) {    let current = 0;    if (s[i - 1] !== "0") current += oneBack;    if (i >= 2) {      const two = Number(s.slice(i - 2, i));      if (two >= 10 && two <= 26) current += twoBack;    }    twoBack = oneBack;    oneBack = current;  }  return oneBack;}console.log(numDecodings("12"));  // 2console.log(numDecodings("226")); // 3console.log(numDecodings("06"));  // 0
How it works

At i = 1 the two-digit case is skipped, and twoBack is set correctly by the end of that step. The time is O(n) and the space is O(1).

Which approach should you use?

Both are fine. Write the two-variable version once you trust the formula. It has the same shape as climbing stairs, with a validity check at each step. (LeetCode 91.)

Q5Word breakMedium

Given a string s and a list of words, return true if s can be split into one or more dictionary words in a row. A word can be used more than once.

Example 1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: leet + code.
Example 2
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: apple + pen + apple. A word can be used more than once.
Example 3
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: cats + and + og fails, and cat + sand + og fails. No word covers the last part, og.
Stuck? Open one hint at a time
Hint 1
State: dp[i] is true when the first i characters can be split into words.
Hint 2
The last word is s[j..i). What must be true about j and about that slice of the string?
Hint 3
Put the dictionary into a Set so lookups are fast.
Show all 2 solutions with explanations
Approach 1Recursion with memo
The idea

canBreak(start) asks whether the rest of the string, from start, can be split. Try each end. If s[start..end) is a word and the rest works, the answer is true. Save the answer for each start. Failed tries are what make the plain recursion so slow.

JavaScript
function wordBreak(s, wordDict) {  const words = new Set(wordDict);  const memo = new Map();  function canBreak(start) {    if (start === s.length) return true;    if (memo.has(start)) return memo.get(start);    let ok = false;    for (let end = start + 1; end <= s.length && !ok; end++) {      if (words.has(s.slice(start, end)) && canBreak(end)) ok = true;    }    memo.set(start, ok);    return ok;  }  return canBreak(0);}console.log(wordBreak("leetcode", ["leet", "code"]));                       // trueconsole.log(wordBreak("applepenapple", ["apple", "pen"]));                  // trueconsole.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false
How it works

There are n starting points, and each tries up to n ends with a slice. That is O(n²) slices, or about O(n³) work on characters. Without the memo, a string like "aaaa...ab" with the word "a" repeats the same failing end part an enormous number of times.

Approach 2Table (bottom-up)
The idea

dp[i] is true if some j < i has dp[j] true and s[j..i) is in the dictionary. We can limit j to the length of the longest word.

JavaScript
function wordBreak(s, wordDict) {  const words = new Set(wordDict);  const longest = Math.max(...wordDict.map((w) => w.length));  const dp = new Array(s.length + 1).fill(false);  dp[0] = true;  for (let i = 1; i <= s.length; i++) {    for (let j = Math.max(0, i - longest); j < i; j++) {      if (dp[j] && words.has(s.slice(j, i))) { dp[i] = true; break; }    }  }  return dp[s.length];}console.log(wordBreak("leetcode", ["leet", "code"]));                       // trueconsole.log(wordBreak("applepenapple", ["apple", "pen"]));                  // trueconsole.log(wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false
How it works

There are O(n × L) slices, where L is the length of the longest word. The space is O(n). For "leetcode": dp[4] = true (leet). dp[8] = true because dp[4] is true and "code" is a word.

Which approach should you use?

Either one is accepted. The table is easier to think about, and the longest-word limit is a cheap way to go faster. (LeetCode 139.)

Q6Longest increasing subsequenceMedium

Given an array of whole numbers, return the length of the longest strictly increasing subsequence (every number is bigger than the one before).

Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: One longest chain is 2, 3, 7, 101 (or 2, 5, 7, 18).
Example 2
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: 0, 1, 2, 3.
Example 3
Input: nums = [7,7,7,7]
Output: 1
Explanation: The chain must be strictly increasing, so equal values cannot be added to it.
Stuck? Open one hint at a time
Hint 1
A subsequence skips some items but keeps the order. Try to define dp[i] as the best chain that ends exactly at i.
Hint 2
To end at i, look at every j before it where nums[j] < nums[i].
Hint 3
The answer is the largest dp[i], not dp[n - 1].
Show all 2 solutions with explanations
Approach 1Take or skip with memo
The idea

best(i, prev) is the longest chain you can make from item i onward, when the last kept position is prev. Either skip item i, or keep it if it is larger than nums[prev]. Save the answers by (i, prev).

JavaScript
function lengthOfLIS(nums) {  const n = nums.length;  const memo = new Map();  function best(i, prev) {                       // prev = -1 means nothing kept yet    if (i === n) return 0;    const key = i * (n + 1) + (prev + 1);    if (memo.has(key)) return memo.get(key);    let result = best(i + 1, prev);              // skip i    if (prev === -1 || nums[prev] < nums[i]) {      result = Math.max(result, 1 + best(i + 1, i));  // keep i    }    memo.set(key, result);    return result;  }  return best(0, -1);}console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));           // 4console.log(lengthOfLIS([7, 7, 7, 7]));                  // 1
How it works

Without the memo, the recursion tries all 2n subsequences. With the memo there are O(n²) states and each takes O(1). So the time and space are O(n²).

Approach 2dp[i] = best chain ending at i
The idea

Every item starts as a chain of length 1. For each earlier, smaller nums[j], set dp[i] = max(dp[i], dp[j] + 1). Return the biggest value in the table.

JavaScript
function lengthOfLIS(nums) {  const dp = new Array(nums.length).fill(1);  let best = 0;  for (let i = 0; i < nums.length; i++) {    for (let j = 0; j < i; j++) {      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);    }    best = Math.max(best, dp[i]);  }  return best;}console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]));           // 4console.log(lengthOfLIS([7, 7, 7, 7]));                  // 1
How it works

The time is O(n²) and the space is O(n). For [10,9,2,5,3,7,101,18] the table is 1, 1, 1, 2, 2, 3, 4, 4. A method with binary search gets O(n log n). See lesson 57.

Which approach should you use?

Use the “ends at i” table. It is simple and fine for n up to a few thousand. If n reaches 105, you need the O(n log n) method in lesson 57. (LeetCode 300.)

Q7Maximum product subarrayMedium

Given an array of whole numbers, find the subarray (one unbroken piece, at least one item) with the largest product, and return that product.

Example 1
Input: nums = [2,3,-2,4]
Output: 6
Explanation: The subarray [2,3] has product 6.
Example 2
Input: nums = [-2,0,-1]
Output: 0
Explanation: Any subarray that includes the 0 gives 0. [-2] and [-1] are negative.
Example 3
Input: nums = [-2,3,-4]
Output: 24
Explanation: Take the whole array: (-2) × 3 × (-4) = 24. Two negative numbers multiply to a positive number.
Stuck? Open one hint at a time
Hint 1
Try the max-sum idea: the best product ending at i. What goes wrong?
Hint 2
A very negative product can become the largest after you multiply it by another negative number. So also keep track of the smallest product ending at i.
Hint 3
At each item there are three choices: the item alone, max × item, or min × item.
Show all 2 solutions with explanations
Approach 1Brute force over all subarrays
The idea

For each start position, move the end forward while you multiply a running product. Remember the largest product.

JavaScript
function maxProduct(nums) {  let best = -Infinity;  for (let start = 0; start < nums.length; start++) {    let product = 1;    for (let end = start; end < nums.length; end++) {      product *= nums[end];      best = Math.max(best, product);    }  }  return best;}console.log(maxProduct([2, 3, -2, 4])); // 6console.log(maxProduct([-2, 0, -1]));   // 0console.log(maxProduct([-2, 3, -4]));   // 24
How it works

The time is O(n²) and the space is O(1). It is correct, but too slow for large inputs.

Approach 2Track the max and the min ending here
The idea

Keep curMax and curMin. These are the largest and smallest products of a subarray that ends at the current item. A negative number swaps their roles. So the new values come from the item alone, curMax * x and curMin * x.

JavaScript
function maxProduct(nums) {  let curMax = nums[0], curMin = nums[0], best = nums[0];  for (let i = 1; i < nums.length; i++) {    const x = nums[i];    const a = curMax * x, b = curMin * x;    curMax = Math.max(x, a, b);              // start fresh at x, or extend    curMin = Math.min(x, a, b);    best = Math.max(best, curMax);  }  return best;}console.log(maxProduct([2, 3, -2, 4])); // 6console.log(maxProduct([-2, 0, -1]));   // 0console.log(maxProduct([-2, 3, -4]));   // 24
How it works

On [-2,3,-4]: after -2 the pair is (-2,-2). At 3 it is (3,-6). At -4 it is (24,-12), so the answer is 24. A zero resets both to 0, and the next item starts fresh. The time is O(n) and the space is O(1).

Which approach should you use?

The max and min pair is the expected answer. You need the min only because a negative number can flip it into the next maximum. (LeetCode 152.)

Make it stick

Make it stick — close this page, then
  1. Finish the sentence “dp[i] means …” for house robber, coin change and LIS (longest increasing subsequence).
  2. Write house robber with two variables and say why two are enough.
  3. Explain how a circle becomes two straight rows in house robber II.
  4. Say why coin change fills the table with Infinity, and when you change it to -1.
  5. Name the two cases that add up in decode ways, and say when each one is valid.
  6. Write word break and LIS, and give their time costs.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

So far every state had one index. Lesson 56 adds a second index. You get a grid of subproblems, used for paths on a board and for the knapsack family of problems, where you choose items without going over a size limit (the capacity).

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series