零钱兑换

问题描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

问题分析

  • 典型的动态规划
  • 典型的完全背包问题

策略选择

  • 动态规划
    • 采取两个方向上的动态规划。两个方向上的动态规划是非等价独立的。
  • 数组矩阵线性数据结构

算法设计

  • 阶段划分：规模增长的方向有两个。第一个规模增长的方向是硬币的种类。第二个规模增长的方向是金钱的总量。

  • 状态变量dp[i][j]表示使用第i个硬币，达到j分钱所有的可能。

  • 状态转移方程

    • if k*coins[i]== amount dp[i][j]++;
    • if kcoins[i]<amount dp[i][j]+=dp[i-1][j-kconis[i]] foreach k

  • 边界条件

    • 当amount=0应该只有一种策略，一个不选。当amount=n、i=coins.size()终止

  • 补充：可以对状态空间进行压缩，提出了一种改进方案。直接以硬币的数目作为第二层遍历。

算法分析

时间复杂度O(mn)
空间复杂度O(mn)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
// 其实就是个很简单的完全背包问题。完全可以设置两个规模增长方向
    int change2(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int& coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
// 使用两个规模增长方向
    int change(int amount, vector<int>& coins) {
        if(amount==0)return 1;
        vector<vector<int>> dp(coins.size()+1,vector<int>(amount + 1,0));
        for (int k=1;k<=coins.size();k++) {
            int coin=coins[k-1];
            for(int i=1;i<=amount;i++){
                for(int j=0;j*coin<=i;j++){
                    if(j*coin==i){
                        dp[k][i]++;
                    }
                    dp[k][i]+=dp[k-1][i-j*coin];
                }
            }
        }
        return dp[coins.size()][amount];
    }
};