Lessons from Counting Knapsack

Three things to remember:

$1.$ Combinations vs permutations is controlled by loop order. Coins $outer = combinations$. Amount $outer = permutations$. This is the most common bug in counting DP.

$2.$ Forward vs backward inner loop depends on bounded vs unbounded. Bounded (use each item once) needs backward. Unbounded (unlimited use) can go forward.

$3.$ Base case for counting is $dp[0] = 1$, not 0. There's exactly one way to make sum 0: use nothing.