题解 | #兑换零钱(二)#

题目分析

1. 题目给出了一个target目标钱数，和一个nums数组，其中元素代表是硬币的币值
2. 题目说不同硬币的币值可以无限次挑选
3. 题目要求返回凑出target目标数的硬币挑选方案的数量

方法一：动态规划

• 实现思路
  • 我们规定dp[i][j]表示在前i种硬币中挑选，凑出j的方案数，最终返回结果是dp[len(nums)][target]
  • 因此对于每一个dp[i][j]我们知道
    • 第i个硬币选择0个，有dp[i][j] = dp[i-1][j]
    • 第i个硬币选择1个，有dp[i][j] = dp[i-1][j-nums[i-1]]
    • 第i个硬币选择k个，有dp[i][j] = dp[i-1][j-k*nums[i-1]]
  • 状态转移方程有
  $dp[i][j]=\sum _{k=0}^{k\times nums[i]\le j}dp[i-1][j-k\times nums[i-1]]dp[i][j]\; =\; \backslash sum\_\{k=0\}^\{k\times nums[i]\backslash le\; j\}dp[i-1][j-k\times nums[i-1]]$

  • 初始化条件dp[0][0]=1，对于0种硬币凑出0价值，只有一种方案

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def change(self , target: int, nums: List[int]) -> int:
        # write code here
        dp = [[0]*(target+1) for _ in range(len(nums)+1)]
        dp[0][0] = 1 # 用前0个元素凑0元有且只有一种方法
        for i in range(1, len(nums) + 1):
            value = nums[i-1]
            for j in range(target + 1):
                k = 0 # 挑选value的硬币数量
                while k*value <= j:
                    dp[i][j] += dp[i-1][j-k*value]    # 迭代将挑新的硬币数量为0，1，2...都统计起来
                    k += 1
        return dp[len(nums)][target]

复杂度分析

• 时间复杂度：$O(targe{t}^2\times n)O(target^2\times n)$，其中$targettarget$是目标凑出来的值，$nn$是硬币数组的总长度
• 空间复杂度：$O(target\times n)O(target\times n)$，其中$targettarget$是目标凑出来的值，$nn$是硬币数组的总长度

方法二：动态规划+时间优化

• 实现思路
  • 由于上一个动态规划中，我们有一部分代价在迭代相加第i种硬币选择k数量的情况，这造成了很大的时间开销
  • 我们可以发现dp[i][j-nums[i-1]]就能代表所有的相加之和的部分。具体理解起来就是，由于我们的硬币挑选可以无限次，所以我们不要直接去找dp[i-1]的部分，dp[i][j-nums[i-1]]表示我在挑选了一枚第i个硬币后，我还可以在前i个硬币中继续挑选，因此省去了大量将k=1,2,...相加的工作
  • 数学推导如下
    • dp[i][j] = dp[i-1][j] + dp[i-1][j-v] + dp[i-1][j-2v] + ... + dp[i-1][j-kv])
    • dp[i][j-v] = dp[i-1,[j-v] + dp[i-1][j-2v] + ... + dp[i-1][j-kv])
  • 因此dp[i][j] = dp[i-1][j] + dp[i][j-v]
  $dp[i][j]=dp[i-1][j]+dp[i][j-v]if:j>=vdp[i][j]\; =\; dp[i-1][j]\; +\; dp[i][j-v]\; \backslash ;\backslash ;\backslash ;\backslash ;if:j>=v$

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def change(self , target: int, nums: List[int]) -> int:
        # write code here
        dp = [[0]*(target+1) for _ in range(len(nums)+1)]
        # 前0,1,2...,len(nums)个元素凑出0的方案为1种
        for i in range(len(nums)+1):
            dp[i][0] = 1
        for i in range(1, len(nums)+1):
            value = nums[i-1]
            for j in range(1, target+1):
                if j >= value:
                    dp[i][j] = dp[i-1][j] + dp[i][j-value]	# dp[i][j-value]表示虽然减去了一次挑选value值硬币的尝试，但是我还可以在前i种硬币中继续挑选，因此解决了可以无限次挑选同一种硬币的问题
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[len(nums)][target]

复杂度分析

• 时间复杂度：$O(target\times n)O(target\times n)$，其中$targettarget$是目标凑出来的值，$nn$是硬币数组的总长度
• 空间复杂度：$O(target\times n)O(target\times n)$，其中$targettarget$是目标凑出来的值，$nn$是硬币数组的总长度

方法三：动态规划+时间优化+空间优化（滚动数组）

• 实现思路

  • 因为我们看到dp转移的过程中当前行的状态只跟前一行有关系，因可以用滚动数组的方式减少空间开销

  • 将二维数组转化为一维数组，具体实现可以与方法二对比

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def change(self , target: int, nums: List[int]) -> int:
        # write code here
        dp = [0]*(target+1) 
        # 前0,1,2...,len(nums)个元素凑出0的方案为1种
        dp[0] = 1
        for i in range(1, len(nums)+1):
            value = nums[i-1]
            for j in range(value, target+1):
                dp[j] = dp[j] + dp[j-value]
        return dp[target]

复杂度分析

• 时间复杂度：$O(target\times n)O(target\times n)$，其中$targettarget$是目标凑出来的值，$nn$是硬币数组的总长度
• 空间复杂度：$O(target)O(target)$，其中$targettarget$是目标凑出来的值，$nn$是硬币数组的总长度，二维数组空间代价用一维数组滚动数组代替