DSA Notes

Dynamic Programming

Changing the State

Swap what the DP indexes with what it stores.

The idea

The usual knapsack table is indexed by weight and stores the best value. If weights go up to 10⁹ that table cannot exist, but when the values are small you can index by value and store the minimum weight needed to reach it.

The answer is then the largest value whose minimum weight fits in the bag.

The same move speeds up longest increasing subsequence: instead of “best length ending at i”, keep for each length the smallest possible last element, and binary-search it. O(n²) becomes O(n log n).

Sample problem

300. Longest Increasing Subsequence ↗ Medium

Return the length of the longest strictly increasing subsequence of an array.

nums = [10,9,2,5,3,7,101,18]
output = 4   (2, 3, 7, 18)

Why the solution works

The direct DP, f[i] = longest increasing subsequence ending at index i, looks back at every earlier index: O(n²).

Swap what is indexed with what is stored. Index by length and store the smallest possible last value of an increasing subsequence of that length. A smaller end can be extended by more numbers, so it is the only one worth keeping.

That array is always sorted. Each new number finds its place by binary search: it either extends the longest subsequence or lowers the end for some length.

Complexity: O(n log n) time, O(n) memory.

Watch out

  • Read the constraints to see which quantity is small; that one becomes the index.
  • In a 0/1 knapsack over one array, loop the index downwards or an item is used twice.
  • INF plus a weight must not overflow: pick INF with room to spare.
Watch it run

Try your own input

Practise on LeetCode