Advanced DP Checkpoint

1. For 0/1 knapsack in 1D DP, you iterate capacity:

Backward (from C to w) Forward (from 0 to C) Random order Only once

2. Bitmask DP over n items has how many states?

2^n n^2 n! n log n

3. Tree DP often uses take/skip states to handle adjacency.

4. Interval DP typically chooses:

A split point inside the interval The global minimum only The earliest start only The last element only

5. Counting LIS uses:

Length and count arrays Only a stack Only a heap Greedy only