找零钱问题动态规划

找零钱问题是一个经典的动态规划问题，其思路是通过不断减小问题规模，最终得出最优解。

具体来说，我们可以定义一个数组 dp，其中 dp[i] 表示凑出金额 i 所需的最少硬币数。那么我们可以考虑从凑出金额 0 开始，逐步增大金额，直到凑出目标金额。

对于每个金额 i，我们可以枚举可用的硬币面值 coins[j]，然后计算凑出金额 i-coins[j] 所需的最少硬币数，即 dp[i-coins[j]]，然后再加上一枚面值为 coins[j] 的硬币即可。这样我们就得到了所有凑出金额 i 所需的硬币数，取其中的最小值即可。

最终，dp[amount] 就是凑出目标金额所需的最少硬币数。

代码实现如下：

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1);
    dp[0] = 0;
    for(int i=1; i<=amount; i++) {
        for(int j=0; j<coins.size(); j++) {
            if(coins[j] <= i) {
                dp[i] = min(dp[i], dp[i-coins[j]]+1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

该算法的时间复杂度为 O(amount*n)，其中 n 是硬币的数量。