@jedihy Yes as @victorfei said the worst-case time complexity is the same as DFS (the DP solution) but it is faster in practice to find the shortest path with BFS. I'm not sure if there is an average-case proof somewhere...
@zhuyinghua1203 This is the best solution I have seen, better than the DP ones. If my understanding is correct then it is efficient because of optimally exploring the tree. In particular it explores branches by using as many of the largest coins as possible before moving on to smaller denominations. It also stops exploring when the branch could not give a better result than already found.
Because of the optimal ordering it does not store the results of subproblems in a lookup table like DP. I wonder if storing any partial results could improve it further?
Also there is no need to put the call to dfs(i, amount, 0) inside a for loop and try all coins. If you change it to dfs(0, amount, 0) it will start with the largest coin and explore all others.