# 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,

**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.**

*k**P(a, k) = min{ P(a, k-1), P(a-cost[k],k)+1 }.*

The complexity is O(amount * k).