322. 零钱兑换(最短路做法leetcode)

322. 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 使用图的方式解决
        // 最短路问题,总金额从0到amount需要走多少步
        // 每一步能迈向的点都是面额里的点+出发点
        // 每步的边权都是1,重要的是走到amount这个顶点,因此可以用bfs
        Deque<int[]> q = new ArrayDeque<>(); // 当前已凑金额
        boolean[] vis=new boolean[amount+1];
        q.add(new int[]{0,0}); // 当前金额顶点,当前步数
        vis[0]=true;
        while(!q.isEmpty())
        {
            int[] t = q.pop();
            if(t[0]==amount)return t[1];
            for(int coin:coins) // 遍历边
            {
                if(coin > amount-t[0] || vis[t[0]+coin]==true ) continue; // 超过答案 或者当前点已遍历过
                vis[t[0]+coin]=true;
                q.add(new int[]{t[0]+coin,t[1]+1});
            }
        }
        return -1; // 无法找到答案

    }
}