DP Techniques Overview

Here's what you'll learn:

$1.$ Bitmask DP tracks subset states in $O(2^n)$ space. Use it when $n \le 20$ and you need to track which elements are chosen.

$2.$ Digit DP counts numbers digit by digit. Use it for problems asking how many integers in a range satisfy some property.

$3.$ Interval DP solves range problems by splitting into subranges.

$4.$ Tree DP processes nodes bottom-up, combining child results.

$5.$ Contribution DP counts how much each element contributes to the total answer.