Skip to content

Index DP with Small Rolling State

Problem

When you see "number of ways", "maximum non-adjacent sum", "choice at each position depends only on previous few positions"

Strategy: Index DP with Small Rolling State

  • Think about this
    • This is likely DP on index.
    • Ask:
      • what is dp[i]
      • what are the last one or two states needed
    • Typical recurrence forms:
      • by last move
      • take or skip current item
  • Avoid this
    • Do not enumerate all paths/sequences.
    • Do not use naive recursion without memoization.
    • Do not keep a full DP array if only two previous states are needed.
  • Tell this to the interviewer
    • Say the recurrence before code.
    • Then compress space if possible from array to two variables.
  • See these problems