Skip to content

Topic 17 of 20

Dynamic Programming – 1D

Recursion plus memory: define a state, write the recurrence, fill the table.

25 problems4 Easy17 Medium4 Hard

The concept

Dynamic programming (DP) solves problems made of overlapping subproblems by solving each subproblem once and storing the answer. If your backtracking solution keeps recomputing the same calls, DP is the fix. A DP solution has three parts: a state (what does dp[i] mean, in one precise sentence?), a recurrence (how is dp[i] built from smaller states?), and base cases.

There are two ways to implement it. Top-down (memoisation) is your recursive solution plus a cache, and it is usually the easiest place to start. Bottom-up (tabulation) fills an array in order. It avoids recursion limits and often lets you shrink memory to a few variables. In interviews, starting top-down and then converting to bottom-up is a strong way to show understanding.

In 1D DP the state is a single index or amount. Learn the families here (Fibonacci-style steps, take-or-skip, 0/1 and unbounded knapsack, longest increasing subsequence, segmentation) and most new DP problems will turn out to be one of them in disguise.

Patterns you will learn

Problems, in order

  1. 1

    The 'hello world' of DP.

    Fibonacci-style RecurrenceReported at: AmazonMicrosoftGoogle+4
  2. 2

    Adds costs to the stair recurrence.

    Fibonacci-style RecurrenceReported at: AmazonAdobeBloomberg
  3. 3

    Rolling variables for O(1) space.

    Fibonacci-style RecurrenceReported at: Amazon
  4. 4

    Building each row from the previous one.

    Row-by-row ConstructionReported at: AmazonAppleMicrosoft+3
  5. 5

    The canonical take-or-skip recurrence.

    Take / Skip (House Robber)Reported at: AmazonAppleGoogle+6
  6. 6

    Handle a circle by solving two linear cases.

    Take / Skip (Circular)Reported at: GoogleAmazon
  7. 7

    Reduces to House Robber after bucketing values.

    Take / Skip (House Robber)Reported at: AmazonGoogleGoldman Sachs
  8. 8

    Counting decodings with validity checks; asked often at Meta.

    Fibonacci-style RecurrenceReported at: AmazonGoogleMeta+5
  9. 9

    Minimum coins, the classic unbounded knapsack.

    Unbounded KnapsackReported at: AmazonMicrosoftGoogle+3
  10. 10

    Counting combinations, where loop order matters.

  11. 11

    Counting ordered sequences; contrast it with Coin Change II.

    Unbounded Knapsack (Permutations)Reported at: AmazonGoogleMeta+1
  12. 12

    Minimum squares, with a BFS alternative.

    Unbounded KnapsackReported at: GoogleAmazonApple+1
  13. 13

    Subset sum with a boolean 0/1 knapsack.

    0/1 KnapsackReported at: MetaMicrosoftAmazon+3
  14. 14

    Reducing ± signs to a subset-sum count.

    0/1 Knapsack (Counting)Reported at: MetaAmazonGoogle+2
  15. 15

    Choosing between pass durations over a calendar.

  16. 16

    Track both max and min because negatives flip signs.

    Kadane VariantsReported at: AmazonMicrosoftGoogle+4
  17. 17

    Circular max = total − minimum subarray.

    Kadane VariantsReported at: AmazonGoogle
  18. 18

    Segmentation DP; one of the most-asked DP problems.

    Word Break / SegmentationReported at: AmazonMetaApple+5
  19. 19

    O(n²) DP and the O(n log n) patience-sorting method.

  20. 20

    Expand around centres, or interval DP.

    Palindromic Substrings (Expand)Reported at: AmazonMicrosoftGoogle+6
  21. 21

    Counting all palindromic substrings.

    Palindromic Substrings (Expand)Reported at: MetaX (Twitter)
  22. 22

    Memoised enumeration of all segmentations.

    Word Break + BacktrackingReported at: MetaAmazonApple+5
  23. 23

    Sort cleverly, then run LIS.

    Longest Increasing Subsequence (2D)Reported at: GoogleByteDance / TikTok
  24. 24

    Weighted interval scheduling; asked frequently at Google and Amazon.

  25. 25

    State design with a hash map of reachable jumps.

    DP over (Position, Last Jump)Reported at: AmazonMicrosoftGoogle+1