TRT
Sign in

Advanced · Module 15 · Lesson 3 of 6

One-dimensional problems

Many problems over a sequence have a DP with one cell per position: the best answer for the prefix ending there. Take-or-skip, counting the ways, and best-ending-here cover most of them.

Pro — members onlyAbout 15 minutes

By the end you can

  • Define dp[i] over prefixes of a sequence and write take-or-skip recurrences
  • Count ways with a recurrence that adds the possibilities for the last step
  • Use best-ending-here states, as in maximum subarray and longest increasing subsequence

Builds on Bottom-up tables.

01 · A question first

A robber can't rob two neighboring houses. On a street of 100 houses there are about a billion trillion allowed sets of houses to choose from. Yet the best plan comes from one pass that, at each house, compares just two numbers. Which two?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • One cell per position
  • Take or skip
  • Counting the ways
  • Best ending here
  • Common pitfalls
  • Recognizing the shape
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeHouse robberMaximize the loot from houses on a street without robbing two neighbors, with a take-or-skip recurrence.Practice · medium · LeetCodeHouse robber IIRob houses arranged in a circle by solving the straight-line problem twice, once without the first house and once without the last.Practice · medium · LeetCodeDecode waysCount the ways to decode a digit string into letters, adding the counts for one-digit and two-digit last letters.Practice · medium · LeetCodeMaximum subarrayFind the largest sum of a contiguous subarray in O(n) with Kadane's best-ending-here recurrence.Practice · medium · LeetCodeWord breakDecide whether a string can be split into dictionary words with a DP over prefixes.Practice · medium · LeetCodeLongest increasing subsequenceFind the length of the longest strictly increasing subsequence, in O(n²) with DP and in O(n log n) with patience tails.

Asked in interviews

Something wrong with this lesson? Report a problem