322. Coin Change
This is an optimization problem. We can always enumerate all solutions and find the result which can simply be achieved via a systematic search like backtrack. The time and space complexity is O(amount * n) and O(n) respectively.
Of course, we need a more efficient algorithm. The problem can also be modeled as a multi-decision problem. We formulate each solution as a decision sequence {a1, a2, a3, …, an} where ai stands for the number of coins[i] used. Can we use some smart method to find ai directly? Such as Greedy. We first pick as many coins[n] as we can, and try coins[: n-1] on the remaining amount(amount-coins[n]*cost[n]). We soon find it doesn’t work. But we find Dynamic Programming can be used since the problem is a multi-decision and an optimization problem. The state transfer function is:
P(a, k) = min{ P(a, k-1), P(a-cost[k]*n, k-1) + n for all possible n }
where a is the amount, k is the kind of coins allowed. Soon I got a TLE. The complexity is O(amount * k * amount). Can we further reduce the complexity. Yeah, by either reduce the state space or the number of links.
P(a, k) = min{ P(a, k-1), P(a-cost[k],k)+1 }.
The complexity is O(amount * k).
