算法学习笔记（8.5）-零钱兑换问题二

目录

Question：

动态规划思路：

代码实现：

空间优化代码

Question：

给定n种硬币，第i种硬币的面值为coins[i-1],目标金额为amt，每种硬币可以重复选取，问凑出目标金额的硬币组合数量。

动态规划思路：

相比与上一题，本体的目标是求组合数量，因此子问题变为：前i种硬币能够凑出金额a的组合数量。而dp的尺寸仍然是（n+1）*（amt+1）的二维矩阵。

当前状态的组合数量等于不选当前硬币与选当前硬币这两种决策的组合数量的和。状态转移方程为：

dp[i，a] = dp[i-1，a] + dp[i，a-coins[i-1]]

当前目标金额为0时，无须选择任何硬币凑出目标金额，因此应将首列所有dp[i，0]都初始化为1。当无硬币时，无法凑出任何>0的目标金额，因此首行的所有的dp[0,a]都等于0。

代码实现：

# python 代码实现
def coin_change_two_dp(coins, amt) :
    n = len(coins)
    dp = [ [0] * (amt + 1) for _ in range(n + 1)]
    for i in range(1, n + 1) :
        dp[i][0] = 1 ;
    for j in range(1, amt + 1) :
        dp[0][j] = 0 ;
    for i in range(1, n + 1) :
        for j in range(1, amt + 1) :
            if coins[i - 1] > j :
                dp[i][j] = dp[i - 1][j]
            else :
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
    return dp[n][amt]

// c++ 代码示例

int coinChangeTwoDP(vector<int> &coins, int amt)
{
    int n = coins.size() ;
    vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0)) ;
    for (int i = 1 ; i <= n ; i++)
    {
        dp[i][0] = 1 ;
    }
    for (int j = 1 ; j <= amt ; j++)
    {
        dp[0][j] = 0 ;
    }
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = 1 ; j <= amt ; j++)
        {
            if (coins[i - 1] > j)
            {
                dp[i][j] = dp[i - 1][j] ;
            }
            else
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]] ;
            }
        }
    }
    return dp[n][amt] ;
}

空间优化代码：

# python 代码示例

def coin_change_two_dp_comp(coins, amt) :
    n = len(coins)
    
    dp = [0] * (amt)
    
    dp[0] = 1
    for i in range(1, n + 1) :
        for j in range(1, amt + 1) :
            if coins[i - 1] > j :
                dp[j] = dp[j]
            else :
                dp[j] = dp[j] + dp[j - coins[i - 1]]
    return dp[amt]

// c++ 代码示例
int coinChangeTwoDPComp(vector<int> &coins, int amt)
{
    int n = coins.size() ;
    vector<int> dp(amt + 1, 0) ;
    dp[0] = 1 ;
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = 1 ; j <= amt; j++)
        {
            if (coins[i - 1] > j)
            {
                dp[j] = dp[j] ;
            }
            else
            {
                dp[j] = dp[j] + dp[j - coins[i - 1]] ;
            }
        }
    }
    return dp[amt] ;
}