leetcode.322.零钱兑换(分支裁剪法)

零钱兑换

322.零钱兑换

剪枝

当 amount==0amount==0 时剪枝，因为大面值硬币需要更多小面值硬币替换，继续减少一枚或几枚大硬币搜索出来的答案【如果有】肯定不会更优。

当 amount!=0，但已经使用的硬币数 cnt 满足了 cnt+1>=ans 时剪枝，因 amount 不为 0，至少还要使用 1 枚硬币，则继续搜索得到的答案不会更优。是 break 不是 continue，因为少用几枚面值大的硬币搜索出的方案【如果有】肯定需要更多枚面值小的硬币来替换掉这枚大的硬币【同剪枝 1 理由】，而使用这几枚大的硬币都搜索不到更好的解，故应该是 break。

代码

class Solution {
public:
  int ans = INT_MAX;
  void dfs( vector<int>& coins, int amount,int index,int cnt)
  {
    if (index < 0) {
      return;
    }
    for (int c = amount / coins[index]; c >= 0; c--)
    {
      int na = amount - c * coins[index];
      int ncnt = cnt + c;
      if (na == 0) {
        ans = ncnt < ans ? ncnt : ans;
        break;//剪枝1
      }
      if (ncnt + 1 >= ans) {
        break; //剪枝2
      }
      dfs(coins, na, index - 1, ncnt);
    }
  }
  int coinChange(vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end());

    dfs( coins, amount, coins.size() - 1,0);
    if (ans == INT_MAX)
    {
      return -1;
    }
    return ans;
  }
};