Leetcode上有几道换零钱(银币)的问题，属于中低频，属于历史上常考的题型之一。
    总共有以下三种描述：

    • 给出零钱种类，目标金额，问总的兑换方案数量。
    • 给出零钱种类，目标金额，问最少能兑换到几枚银币。
    • 给出零钱种类，目标金额，目标银币枚数，问总的兑换方案数。

    第一题深搜将超时，但它和完全背包很相似。第二题也和背包问题相似。第三题和组合问题相似用深搜可以。

    1.     int change(int target, vector<int>& money) {
    2.         if (target <= 0) return 1;
    3.         if(money.empty()) return 0;
    4.         int n = money.size();
    5.         vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
    6.         for (int i = 0; i <= n; ++i)
    7.             dp[i][0] = 1;
    9.         for (int i = 1; i <= n; ++i)
    10.             for (int j = 1; j <= target; ++j)
    11.                 for (int k = 0; k <= j / money[i-1]; ++k)
    12.                     dp[i][j] += dp[i - 1][j - k*money[i-1]];
    13.         return dp[n][target];
    14.     }

    第二题(降维的背包问题)

    class Solution {
public:
    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];
    }
};

    用记忆化搜索(备忘录)(深搜+缓存)也特别容易理解：

    class Solution {
    vector<int>count;
    int dp(vector<int>& coins, int rem) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];
        int Min = INT_MAX;
        for (int coin:coins) {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < Min) {
                Min = res + 1;
            }
        }
        count[rem - 1] = Min == INT_MAX ? -1 : Min;
        return count[rem - 1];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;
        count.resize(amount);
        return dp(coins, amount);
    }
};

    很像股票问题的写法。

    第三题(深搜+剪枝)

    //深搜+剪枝
    void dfs(vector<int>& money, vector<int>& cur, vector<vector<int>>& vret, int start, int gap, int k) {
        if (cur.size() == k && gap == 0) {
            vret.push_back(cur);
            return;
        }
        if (cur.size() > k)//剪枝
            return;
        for (int i = start; i < money.size(); ++i) {
            if (money[i] > gap) return;
            cur.push_back(money[i]);
            dfs(money,cur, vret, i,  gap - money[i], amount);
            cur.pop_back();
        }
    }