Multidimensional DP

State variables

The following are common things to look out for in DP problems that require a state variable:

• An index along some input.
  • input: nums = [0, 1, 2, 3, 4, 5, 6]
  • state: dp(4)
    -sub problem: nums = [0, 1, 2, 3]
• A second index along some input.
  • input: nums = [0, 1, 2, 3, 4, 5, 6]
  • state: dp(1, 3)
    • sub problem: nums = [1, 2, 3]
• Explicit numerical constraints given in the problem.
  • “you are only allowed to complete k transactions”,
  • “you are allowed to break up to k obstacles”, etc.
• Variables that describe statuses in a given state.
  • “true if currently holding a key, false if not”,
  • “currently holding k packages” etc.
• Some sort of data like a tuple or bitmask used to indicate things being “visited” or “used”.
  • For example, "bitmask is a mask where the i th bit indicates city has been visited".

Ref

• Multidimensional DP