Editor

Dynamic programming problems in Python

Build answers from the answers to smaller cases: dynamic programming problems in Python, with tests.

Start with Climbing Stairs

Beginner

  1. 41. Climbing StairsHow many different ways can you walk up a staircase?40 XP8 min
  2. 233. Tribonacci NumbersFibonacci's big cousin, who always looks three steps back30 XP5 min
  3. 248. Cheapest Way Up the StairsEvery step charges a toll: what is the cheapest way to the top?40 XP8 min

Intermediate

  1. 71. Maximum Subarray SumThe best unbroken run in a list of ups and downs65 XP10 min
  2. 82. House RobberThe most loot from a street without setting off an alarm70 XP12 min
  3. 90. Grid Paths with WallsCount the routes across a grid when some squares are blocked75 XP14 min
  4. 106. Fewest CoinsThe smallest handful of coins that pays an exact amount85 XP15 min
  5. 111. Ways to Make ChangeHow many different handfuls of coins pay the bill exactly?85 XP15 min
  6. 115. Word BreakCan this run-together text be split into real words?90 XP18 min
  7. 279. Cheapest Path Down a TriangleSlide down a pyramid of numbers, paying for every stone you touch65 XP12 min
  8. 303. Houses in a CircleA thief, a ring of houses and alarms that link every pair of neighbours70 XP12 min
  9. 330. Equal-Sum HalvesCan two friends share the parcels so both carry the same weight?80 XP15 min
  10. 340. Plus or MinusA plus or a minus in front of every number: how many ways hit the total?85 XP16 min

Advanced

  1. 130. Longest Increasing SubsequenceThe longest climb hidden inside a jumbled list120 XP22 min
  2. 135. Longest Common SubsequenceHow much do two strings have in common, in order?125 XP22 min
  3. 141. Decode WaysHow many messages could this string of digits spell?130 XP25 min
  4. 156. Pack the KnapsackThe most valuable load a backpack can carry140 XP25 min
  5. 367. Longest Palindromic SubsequenceCross out letters until the word reads the same both ways130 XP25 min
  6. 375. Interleaving StringsTwo strings woven together: could this string be the result?135 XP25 min
  7. 387. Longest Balanced Bracket RunThe longest stretch where every bracket has its partner140 XP25 min
  8. 398. Health for the DungeonHow much health does the knight need to survive the dungeon?145 XP30 min
  9. 403. Best Profit With K TradesA limited number of trades: when should you buy, and when sell?150 XP30 min
  10. 408. Fewest Palindrome CutsSlice a word into mirror-image pieces with as few cuts as you can150 XP30 min
  11. 413. Most Profitable JobsPick the gigs that pay the most when no two can overlap150 XP30 min

Expert

  1. 174. Edit DistanceThe fewest typo fixes that turn one word into another200 XP30 min
  2. 181. Distinct SubsequencesHow many ways does a word hide inside a longer string?220 XP40 min
  3. 191. Egg DropHow few drops does it take to find the safe floor?250 XP45 min
  4. 197. Regular Expression MatchingDoes the whole string fit a pattern of dots and stars?260 XP50 min
  5. 198. Burst BalloonsPop the balloons in the order that scores the most points280 XP55 min
  6. 434. Frog CrossingStone by stone across the river, each jump a little longer or shorter200 XP35 min
  7. 462. The Delivery TourOne van, every stop once, then back home: the shortest possible round230 XP45 min
  8. 480. The Strange PrinterA printer that paints runs of one letter at a time: how few passes?250 XP45 min
  9. 484. Cherry Picking Round TripDown to the far corner and back again: how many cherries can you pick?260 XP50 min
  10. 494. Shortest SuperstringSqueeze every word into one string, overlapping wherever you can270 XP55 min
  11. 497. Cheapest Way to Merge PilesSquash a row of sand piles into one, a few at a time, for the least effort280 XP55 min
  12. 500. Distinct Palindromic SubsequencesHow many different mirror-image strands hide inside a strand of DNA?290 XP60 min

Other topics

Or see every challenge, with study plans, today's challenge and duels.