力扣322. 零钱兑换

动态规划

• 思路：
  • 假设 dp[i] 表示金额 i 的零钱兑换最小数量；
  • 它可以由 dp[i - C(j)] + 1，即由币值C(j) 与 dp[i - C(j)] 组成，要使得数量最少，则 dp[i - C(j)] 最小；
  • 边界条件 dp[0] = 0；
  • 自下而上分别计算出其需要的数量；
  • 计算某一金额的时候，遍历用币值与其剩余金额数量 + 1，取最小值记录；

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int mark = amount + 1;

        std::vector<int> dp(amount + 1, mark);
        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] = std::min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
};