1 特别注意amount=0的时候,是返回0,不是返回-1
2 以上BFS方法总是超时
3 因为很容易出现之前操作过的再次操作,这样就很耗时,像下图中的9,在第二行访问过,再第三行又出现了,因为之后的操作会是一模一样的,所以用一个visited的数组来存储是否被访问过
1 要注意corner case:当amount==0的时候,返回0,表示有0种组合方式
2 还有就是如果amount在coins中,直接返回1
3 queue中压栈money和dist
4 重点在什么时候加到visited中去,只有没有在visited中,才加入到visited中和放入队列中去
1 当amount是0的时候,返回0,不是-1
2 初始化dp的时候,float("inf")要用中括号括起来
Time complexity:O(amount * n) + O(nlogn) n is the length of coins
Space complexity: O(amount)