LeetCode 322 Coin Change - Example and Complexity Analysis

Trace coins = [1,2,5], amount = 6.

dp[0] = 0 dp[1] = dp[0] + 1 = 1 (use coin 1) dp[2] = min(dp[1]+1, dp[0]+1) = min(2, 1) = 1 (use coin 2) dp[3] = min(dp[2]+1, dp[1]+1) = min(2, 2) = 2 dp[4] = min(dp[3]+1, dp[2]+1) = min(3, 2) = 2 dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = min(3, 3, 1) = 1 (use coin 5) dp[6] = min(dp[5]+1, dp[4]+1, dp[1]+1) = min(2, 3, 2) = 2

Answer: $2$ coins (5 + 1 or 2 + 2 + 2? Actually 5+1=6 is 2 coins).

$O(\text{amount} \times \text{coins})$ time. $O(\text{amount})$ space.