题目

322. 零钱兑换

思路

参考链接
举个例子吧，coins = [1,3,5], amount = 11。
使用最少数目的硬币凑够11元(用函数F(11)表示)，有三种方案：
1，先拿1元，然后凑够剩下10元，并让凑够10元使用的硬币数目最少，用函数F(10)表示；
2，先拿3元，然后凑够剩下8元， 并让凑够8元使用的硬币数目最少，用函数F(8)表示；
3，先拿5元，然后凑够剩下6元，并是凑够6元使用的硬币数目最少，用函数F(6)表示。
三种方法使用的最少银币数目依次为1+F(10)、 1+F(8)、 1+F(6),比较三者大小，选取数目最少的那一种方案。

dp三部曲：a.定义子问题，b. 定义状态数组(目标)，c. 定义状态转移方程。

目标dp[n]定义：凑够n元使用的最少硬币数。
规模较大的问题能拆解为规模小的子问题来递推解决。那就能找状态转移方程啦。

image.png

直接写递归会产生『重叠子问题』，存在大量重复计算，比较低效，我们用dp来解决（自底向上，消除重叠子问题）。

啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「自顶向下」。

啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

dp[1] = dp[0]+1 = 1
dp[2] = min(dp[1]+1, dp[0]+1) = min(2,1) = 1
dp[3] = min(dp[2]+1, dp[1]+1) = 2
dp[4] = min(dp[3]+1, dp[2]+1) = 2
...

代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i < coin) continue;
                dp[i] = min(dp[i], dp[i-coin]+1);
            }
        }
        return dp[amount] > amount ? -1:dp[amount];

    }
};

相似题

279. 完全平方数

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, n+1);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                dp[i] = min(dp[i], dp[i-j*j]+1);
            }            
        }
        return dp[n];
    }
};