LeetCode 322. 零钱兑换(贪心+dfs剪枝)

class Solution {
public:
    int ans;
    void dfs(vector<int>& c, int p, int target, int num){
        if(p < 0) return ;
        for(int i=target/c[p];i>=0;i--){      // 尽量多的去使用当前硬币
            int tmp = target - i * c[p];      // 使用了i个c[p]硬币后的值
            int cnt = num + i;
            if(tmp == 0){                     // 达到目标后直接break
                ans = min(ans, cnt);
                break;
            }
            if(cnt + 1 >= ans) break;         // 没必要再往下搜了
            dfs(c, p - 1, tmp, cnt);
        }
    }
    int coinChange(vector<int>& c, int amount) {
        sort(c.begin(), c.end());
        ans = 0x3f3f3f3f;
        dfs(c, c.size() - 1, amount, 0);
        return ans == 0x3f3f3f3f ? -1 : ans;
    }
};