Leetcode322 零钱兑换

零钱兑换是很经典的题目，今天解题时却出现一些问题，记录一下

首先想到的是广度优先搜索，用queue实现

int coinChange(vector<int>& coins, int amount) {
        queue<vector<int>> nums;
        vector<int> passed;//记录已经搜索过的金额，再次遍历到可直接跳过
        nums.push(vector<int>(coins.size(),0));//插入初始数量，即全是0
        int answer=-1;
        for(;nums.size()>0;){
            answer++;
            int queue_num=nums.size();//存储这一轮所有组合的size
            for(int i=0;i<queue_num;i++){
                int sum=0;
                vector<int> temp=nums.front();
//取出第一个数量组合
                for(int j=0;j<temp.size();j++){
                    sum+=coins[j]*temp[j];//计算总和
                }
                for(auto k:passed){//如果已经搜索过这个sum就跳过
                    if(k==sum)
                        goto here;//goto跳出循环，某些教材写着不要用goto，其实大可不必这么绝对
                }
                passed.push_back(sum);//没有搜索过该sum就插入
                if(sum==amount)
                    return answer;
                if(sum<amount){
                    for(int j=0;j<temp.size();j++){
                        temp[j]++;
                        nums.push(temp);
                        temp[j]--;//记得恢复原样
                    }
                }
                here:nums.pop();//把队头弹出
            }
        }
        return -1;
    }

这么写执行起来没问题，该优化的也优化了，但提交还是超时，后来一想还是没看清题，只要求返回次数，并不要求返回具体的组合，相当于我们把题做复杂了。这题广度优先搜索只用记录sum，不用记录组合，这样就能简化很多。

    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) 
            return 0;
        queue<int> sum;
        int answer=-1;
        vector<int> pass;
        sum.push(0);
        while(sum.size()>0){
            answer++;
            int size0=sum.size();
            for(int i=0;i<size0;i++){
                for(auto j:pass){
                    if(j==sum.front())
                        goto here;
                }
                pass.push_back(sum.front());
                if(sum.front()==amount)
                    return answer;
                else{
                    for(auto j:coins){
                        if(sum.front()<=amount-j)
                            sum.push(sum.front()+j);
                    }
                }
                here:sum.pop();
            }
        }
        return -1;
    }

这样写还是超时，换成自顶向下也不行，看来是优化的方法草率了，换做使用动态规划的思想建立数组记录重复值来进一步优化。

public:
    int coinChange(vector<int>& coins, int amount) {
        pass.resize(amount);
        return find(coins,amount);
    }
    vector<int> pass;
    int find(vector<int>& coins, int am){
        if(am==0)
            return 0;
        if(am<0)
            return -1;
        if(pass[am-1]!=0)
            return pass[am-1];
        int min0=INT_MAX;
        for(auto i:coins){
            int res=find(coins,am-i);
            if(res>=0&&res<min0){
                min0=res+1;
            }
        }
        pass[am-1]=min0==INT_MAX?-1:min0;
        return(pass[am-1]);
    }

或者直接动态规划

int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }