DSA Notes

Dynamic Programming

Non-classic DP

The same recipe, but you have to invent the state yourself.

The idea

Outside the textbook problems there is no formula to recall. Ask: “what do I need to know about the past to make the next decision?” That is the state.

Typical answers: the last choice made (so the next one can differ), an interval [l, r] of a string (palindromes), or both dimensions of a rectangle being cut.

Interval and rectangle DPs are filled from small to large: by length, or by width and height.

Sample problem

198. House Robber ↗ Medium

Houses in a row hold the given amounts of money. Robbing two adjacent houses sets off the alarm. Return the most money that can be taken.

nums = [2,7,9,3,1]
output = 12   (2 + 9 + 1)

Why the solution works

No formula is given here; the state has to be invented. Ask what a decision about house i needs to know about the past: only the best total so far, and the best total that leaves house i−1 alone.

Let f[i] be the best from the first i houses. For house i there are two choices: skip it, keeping f[i−1]; or rob it, which rules out house i−1 and gives f[i−2] + nums[i−1].

The constraint “not two neighbours” is absorbed by reaching back two states instead of one.

Complexity: O(n) time and memory.

Watch out

  • If a transition needs information the state does not hold, add a dimension for it.
  • If the state holds more than the future depends on, the table is bigger and slower than necessary.
  • For interval DP, loop over the length first so shorter intervals are ready.
Watch it run

Try your own input

Practise on LeetCode