题目描述

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:

Input: amount = 10, coins = [10]
Output: 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

有一堆各种面额的硬币coins，给定一个数量，求用不同面额硬币组成这个数量的方法数。每种面额使用数量不限。

解法

这是一道典型的动态规划题，其特征是当前的状态能够由上一个状态推得。
有基本的思想模板：
* 定义答案显而易见的基本情况。
* 制定根据简单的情况计算复杂情况的策略。
* 将此策略链接到基本情况。（by leetcode中国）
我们coins = {1,2,5}，列表

 

先列出coins = {} 的情况，这是答案显而易见的基本情况，需要稍微注意一下的就是amount = 0时，结果为1，即不选。
添加进一种面额 1，coins = {1}, 所有结果均为1.
添加进一种面额2，coins = [1,2}, 考虑如何从没有2时的情况推得，dp[amount] = dp[amount-2](选入2，即2所在的这一行) + dp[amount](没有选入2, 即上一行), 可得递推式, 当amount >= coin 有 dp[amount] += dp[amount-coin]
添加进一种面额5, coins = {1,2,5}, 用递推式得出1-5的结果，容易验证结果正确。

代码

int change(int amount, vector& coins) {
    std::sort(coins.begin(), coins.end(), greater());
    vector dp(amount + 1, 0);
    dp[0] = 1;
    for (auto coin : coins) {
        for (int i = coin; i <= amount; i++)
            dp[i] += dp[i-coin];
    }
    return dp[amount];
}