DP Fundamentals

1. DP is useful when a problem has:

Overlapping subproblems and optimal substructure Only greedy choice No subproblems Randomness

2. Climbing stairs recurrence for dp[i]?

3. For Coin Change (min coins), initialize dp with:

Infinity (large value) 0 amount 1

4. House Robber chooses max of:

rob i + dp[i-2] vs skip i + dp[i-1] dp[i-1]+dp[i-1] dp[i-2]+dp[i-2] always rob i

5. Space optimization that keeps only the last few states is called:

6. In the O(n log n) LIS algorithm, what does the `tails` array represent?