leetcode_零钱兑换Ⅱ

原题链接

1. 题目描述

给定不同面额的硬币coins和一个总金额amount，求出可以凑成总金额的硬币组合数。

举个栗子：

amount = 5, coins = [1, 2, 5]

输出：4

共有四种方式可以凑成总金额：5 = 5; 5= 2 + 2 + 1; 5 = 2 + 1 + 1 + 1 ; 5 = 1 + 1 + 1 + 1 + 1

2. 解题思路

这题和数楼梯非常相似，只是数楼梯是求的排列数，而此时需要求一个组合数，两者代码其实非常相似，请看下述代码（代码摘自leetcode解答）：

class Solution1 {
public:
    int change(int amount, vector<int>& coins) {
        int dp[amount+1];
        memset(dp, 0, sizeof(dp)); //初始化数组为0
        dp[0] = 1;
        for (int j = 1; j <= amount; j++){ //枚举金额
            for (int coin : coins){ //枚举硬币
                if (j < coin) continue; // coin不能大于amount
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};
class Solution2 {
public:
    int change(int amount, vector<int>& coins) {
        int dp[amount+1];
        memset(dp, 0, sizeof(dp)); //初始化数组为0
        dp[0] = 1;
        for (int coin : coins){ //枚举硬币
            for (int j = 1; j <= amount; j++){ //枚举金额
                if (j < coin) continue; // coin不能大于amount
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};

首先非常好理解，Solution1求解的就是排序数（数楼梯思路）

为什么Solution2求解的就是组合数呢？

设问题dp[k, i]表示兑换总金额 i 使用前k个硬币的组合数，则状态方程为：

dp[k, i] = dp[k-1, i] + dp[k, i - k]

要求兑换总金额 i 使用前k个硬币的组合数可以分两种情况

不使用第k个硬币，即dp[k - 1, i]
使用第k个硬币，那么至少使用一个k号硬币，所以此时组合数为dp[k, i - k]

状态方程是一个二维dp过程，但是如果我们一行一行的求解这个二维dp（从左往右，从上往下计算这个二维矩阵），其实可以将其压缩为一维dp，即上述的Solution2代码。

不理解可以试试分析几行~