股票类型题目：121 122 123 188 309 714 剑指offer63
一种常用的方法是将「买入」和「卖出」分开进行考虑：「买入」为负收益，而「卖出」为正收益。在初入股市时，只有「买入」的权利，只能获得负收益。而当「买入」之后，就有了「卖出」的权利，可以获得正收益。显然，需要尽可能地降低负收益而提高正收益，因此目标是将收益值最大化。因此，可以使用动态规划的方法，维护在股市中每一天结束后可以获得的「累计最大收益」，并以此进行状态转移，得到最终的答案。

第一题、123.买卖股票的最佳时机 III

方法、动态规划
思路比较复杂，看官方题解

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)  # 获取价格列表的长度
        buy1 = buy2 = -prices[0]  # 初始化第一次和第二次买入的最大收益为负的第一个价格
        sell1 = sell2 = 0  # 初始化第一次和第二次卖出的最大收益为0
        
        for i in range(1, n):  # 从第二天开始遍历价格列表
            buy1 = max(buy1, -prices[i])  # 更新第一次买入的最大收益，选择更低的买入价格
            sell1 = max(sell1, buy1 + prices[i])  # 更新第一次卖出的最大收益，选择更高的卖出价格
            buy2 = max(buy2, sell1 - prices[i])  # 更新第二次买入的最大收益，利用第一次交易后的收益
            sell2 = max(sell2, buy2 + prices[i])  # 更新第二次卖出的最大收益，选择更高的卖出价格
            
        return sell2  # 返回最大收益，即两次交易后的最大卖出收益

用时和内存

时间复杂度：O(n)，其中 n 是数组 prices 的长度。
空间复杂度：O(1)。

第二题、309. 买卖股票的最佳时机含冷冻期

方法、动态规划
用 f[i] 表示第 i 天结束之后的「累计最大收益」。根据题目描述，由于最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此会有三种不同的状态：
目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i][2]。
这里的「处于冷冻期」指的是在第 i 天结束之后的状态。也就是说：如果第 i 天结束之后处于冷冻期，那么第 i+1 天无法买入股票。
如何进行状态转移呢？在第 i 天时，可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i 天的状态会从第 i−1 天的状态转移而来；也可以不进行任何操作，此时第 i 天的状态就等同于第 i−1 天的状态。那么分别对这三种状态进行分析：
对于 f[i][0]，目前持有的这一支股票可以是在第 i−1 天就已经持有的，对应的状态为 f[i−1][0]；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 f[i−1][2] 加上买入股票的负收益 prices[i]。因此状态转移方程为：
f[i][0]=max(f[i−1][0],f[i−1][2]−prices[i])
对于 f[i][1]，在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时必须持有一支股票，对应的状态为 f[i−1][0] 加上卖出股票的正收益 prices[i]。因此状态转移方程为：
f[i][1]=f[i−1][0]+prices[i]
对于 f[i][2]，在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 f[i−1][1]；如果不处于冷冻期，对应的状态为 f[i−1][2]。因此状态转移方程为：
f[i][2]=max(f[i−1][1],f[i−1][2])
这样就得到了所有的状态转移方程。如果一共有 n 天，那么最终的答案即为：
max(f[n−1][0],f[n−1][1],f[n−1][2])
注意到如果在最后一天（第 n−1 天）结束之后，手上仍然持有股票，那么显然是没有任何意义的。因此更加精确地，最终的答案实际上是 f[n−1][1] 和 f[n−1][2] 中的较大值，即：
max(f[n−1][1],f[n−1][2])

可以将第 0 天的情况作为动态规划中的边界条件：
f[0][0]=−prices[0]
f[0][1]=0
f[0][2]=0
在第 0 天时，如果持有股票，那么只能是在第 0 天买入的，对应负收益 −prices[0]；如果不持有股票，那么收益为零。注意到第 0 天实际上是不存在处于冷冻期的情况的，但仍然可以将对应的状态 f[0][1] 置为零。
这样就可以从第 1 天开始，根据上面的状态转移方程进行进行动态规划，直到计算出第 n−1 天的结果。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:  # 如果价格列表为空，直接返回0
            return 0
        
        n = len(prices)  # 获取价格列表的长度
        # f[i][0]: 第i天手上持有股票的最大收益
        # f[i][1]: 第i天手上不持有股票，并且处于冷冻期中的累计最大收益
        # f[i][2]: 第i天手上不持有股票，并且不在冷冻期中的累计最大收益
        f = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)]  # 初始化状态数组
        for i in range(1, n):  # 从第二天开始遍历价格列表
            f[i][0] = max(f[i - 1][0], f[i - 1][2] - prices[i])  # 计算第i天持有股票的最大收益
            f[i][1] = f[i - 1][0] + prices[i]  # 计算第i天卖出股票后的最大收益，进入冷冻期
            f[i][2] = max(f[i - 1][1], f[i - 1][2])  # 计算第i天不持有股票且不在冷冻期的最大收益
        
        # 返回最后一天，不持有股票时的最大收益，可以是处于冷冻期或非冷冻期
        return max(f[n - 1][1], f[n - 1][2])

用时和内存

空间优化：
注意到上面的状态转移方程中，f[i][..] 只与 f[i−1][..] 有关，而与 f[i−2][..] 及之前的所有状态都无关，因此不必存储这些无关的状态。也就是说，只需要将 f[i−1][0]，f[i−1][1]，f[i−1][2] 存放在三个变量中，通过它们计算出 f[i][0]，f[i][1]，f[i][2] 并存回对应的变量，以便于第 i+1 天的状态转移即可。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:  # 如果价格列表为空，直接返回0
            return 0
        
        n = len(prices)  # 获取价格列表的长度
        f0, f1, f2 = -prices[0], 0, 0  # 初始化三种状态的变量
        for i in range(1, n):  # 从第二天开始遍历价格列表
            newf0 = max(f0, f2 - prices[i])  # 计算第i天持有股票的最大收益
            newf1 = f0 + prices[i]  # 计算第i天卖出股票后的最大收益，进入冷冻期
            newf2 = max(f1, f2)  # 计算第i天不持有股票且不在冷冻期的最大收益
            f0, f1, f2 = newf0, newf1, newf2  # 更新状态变量
        
        return max(f1, f2)  # 返回最后一天，不持有股票时的最大收益，可以是处于冷冻期或非冷冻期

用时和内存

时间复杂度：O(n)，其中 n 为数组 prices 的长度。
空间复杂度：O(n)。需要 3n 的空间存储动态规划中的所有状态，对应的空间复杂度为 O(n)。如果使用空间优化，空间复杂度可以优化至 O(1)。

第三题、188. 买卖股票的最佳时机 IV

方法、动态规划
与其余的股票问题类似，使用一系列变量存储「买入」的状态，再用一系列变量存储「卖出」的状态，通过动态规划的方法即可解决本题。
用 buy[i][j] 表示对于数组 prices[0..i] 中的价格而言，进行恰好 j 笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用 sell[i][j] 表示恰好进行 j 笔交易，并且当前手上不持有股票，这种情况下的最大利润。
那么可以对状态转移方程进行推导。对于 buy[i][j]，考虑当前手上持有的股票是否是在第 i 天买入的。如果是第 i 天买入的，那么在第 i−1 天时，手上不持有股票，对应状态 sell[i−1][j]，并且需要扣除 prices[i] 的买入花费；如果不是第 i 天买入的，那么在第 i−1 天时，手上持有股票，对应状态 buy[i−1][j]。那么可以得到状态转移方程：
buy[i][j]=max{buy[i−1][j],sell[i−1][j]−price[i]}
同理对于 sell[i][j]，如果是第 i 天卖出的，那么在第 i−1 天时，手上持有股票，对应状态 buy[i−1][j−1]，并且需要增加 prices[i] 的卖出收益；如果不是第 i 天卖出的，那么在第 i−1 天时，手上不持有股票，对应状态 sell[i−1][j]。那么可以得到状态转移方程：
sell[i][j]=max{sell[i−1][j],buy[i−1][j−1]+price[i]}
由于在所有的 n 天结束后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好（例如数组 prices 单调递减，不进行任何交易才是最优的），因此最终的答案即为 sell[n−1][0..k] 中的最大值。

在上述的状态转移方程中，确定边界条件是非常重要的步骤。可以考虑将所有的 buy[0][0..k] 以及 sell[0][0..k] 设置为边界。
对于 buy[0][0..k]，由于只有 prices[0] 唯一的股价，因此不可能进行过任何交易，那么可以将所有的 buy[0][1..k] 设置为一个非常小的值，表示不合法的状态。而对于 buy[0][0]，它的值为 −prices[0]，即「在第 0 天以 prices[0] 的价格买入股票」是唯一满足手上持有股票的方法。
对于 sell[0][0..k]，同理可以将所有的 sell[0][1..k] 设置为一个非常小的值，表示不合法的状态。而对于 sell[0][0]，它的值为 0，即「在第 0 天不做任何事」是唯一满足手上不持有股票的方法。
在设置完边界之后，就可以使用二重循环，在 i∈[1,n),j∈[0,k] 的范围内进行状态转移。需要注意的是，sell[i][j] 的状态转移方程中包含 buy[i−1][j−1]，在 j=0 时其表示不合法的状态，因此在 j=0 时，无需对 sell[i][j] 进行转移，让其保持值为 0 即可。
最后需要注意的是，本题中 k 的最大值可以达到 10^9 ，然而这是毫无意义的，因为 n 天最多只能进行 ⌊ n/2 ⌋ 笔交易，其中 ⌊x⌋ 表示对 x 向下取整。因此可以将 k 对 ⌊ n/2 ⌋ 取较小值之后再进行动态规划。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:  # 如果价格列表为空，直接返回0
            return 0

        n = len(prices)  # 获取价格列表的长度
        k = min(k, n // 2)  # 最大交易次数不能超过n // 2，因为一次交易包含一次买入和一次卖出
        buy = [[0] * (k + 1) for _ in range(n)]  # 初始化买入操作的收益数组
        sell = [[0] * (k + 1) for _ in range(n)]  # 初始化卖出操作的收益数组

        buy[0][0], sell[0][0] = -prices[0], 0  # 第一天买入的收益为负的第一个价格，卖出收益为0
        for i in range(1, k + 1):  # 初始化第一天的所有交易次数状态
            buy[0][i] = sell[0][i] = float("-inf")  # 超过交易次数的状态置为负无穷大，不可达

        for i in range(1, n):  # 从第二天开始遍历价格列表
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i])  # 第i天未发生交易时的买入最大收益
            for j in range(1, k + 1):  # 逐步计算第i天每次交易的最大买入和卖出收益
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i])  # 第j次交易的最大买入收益
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i])  # 第j次交易的最大卖出收益  

        return max(sell[n - 1])  # 返回最后一天的最大卖出收益，表示最大利润

用时和内存

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:  # 如果价格列表为空，直接返回0
            return 0

        n = len(prices)  # 获取价格列表的长度
        k = min(k, n // 2)  # 最大交易次数不能超过n // 2，因为一次交易包含一次买入和一次卖出
        buy = [0] * (k + 1)  # 初始化买入操作的收益数组
        sell = [0] * (k + 1)  # 初始化卖出操作的收益数组

        buy[0], sell[0] = -prices[0], 0  # 第一天买入的收益为负的第一个价格，卖出收益为0
        for i in range(1, k + 1):  # 初始化第一天的所有交易次数状态
            buy[i] = sell[i] = float("-inf")  # 超过交易次数的状态置为负无穷大，不可达

        for i in range(1, n):  # 从第二天开始遍历价格列表
            buy[0] = max(buy[0], sell[0] - prices[i])  # 第i天未发生交易时的买入最大收益
            for j in range(1, k + 1):  # 逐步计算第i天每次交易的最大买入和卖出收益
                buy[j] = max(buy[j], sell[j] - prices[i])  # 第j次交易的最大买入收益
                sell[j] = max(sell[j], buy[j - 1] + prices[i])  # 第j次交易的最大卖出收益  

        return max(sell)  # 返回最后一天的最大卖出收益，表示最大利润

用时和内存

时间复杂度：O(nmin(n,k))，其中 n 是数组 prices 的大小，即使用二重循环进行动态规划需要的时间。
空间复杂度：O(nmin(n,k)) 或 O(min(n,k))，取决于使用二维数组还是一维数组进行动态规划。

第四题、714.买卖股票的最佳时机含手续费

本题和 122. 买卖股票的最佳时机 II 是非常类似的题，唯一的区别就在于本题有「手续费」而第 122 题没有。
方法一、动态规划
考虑到「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态。
定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。
考虑 dp[i][0] 的转移方程，如果这一天交易完后手里没有股票，那么可能的转移状态为前一天已经没有股票，即 dp[i−1][0]，或者前一天结束的时候手里持有一支股票，即 dp[i−1][1]，这时候要将其卖出，并获得 prices[i] 的收益，但需要支付 fee 的手续费。因此为了收益最大化，列出如下的转移方程：
dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]−fee}
再来按照同样的方式考虑 dp[i][1] 按状态转移，那么可能的转移状态为前一天已经持有一支股票，即 dp[i−1][1]，或者前一天结束时还没有股票，即 dp[i−1][0]，这时候要将其买入，并减少 prices[i] 的收益。可以列出如下的转移方程：
dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}
对于初始状态，根据状态定义可以知道第 0 天交易结束的时候有 dp[0][0]=0 以及 dp[0][1]=−prices[0]。
因此，只要从前往后依次计算状态即可。由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的，最后的答案即为 dp[n−1][0]。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)  # 获取价格列表的长度
        # 初始化DP数组，dp[i][0]表示第i天不持有股票的最大收益，dp[i][1]表示第i天持有股票的最大收益
        dp = [[0, -prices[0]]] + [[0, 0] for _ in range(n - 1)]
        
        for i in range(1, n):  # 从第二天开始遍历价格列表
            # 计算第i天不持有股票的最大收益，可以是前一天不持有股票，或前一天持有股票今天卖出（减去手续费）的收益
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
            # 计算第i天持有股票的最大收益，可以是前一天持有股票的收益，或前一天不持有股票今天买入的收益
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        
        # 返回最后一天不持有股票的最大收益，即最大利润
        return dp[n - 1][0]

用时和内存

注意到在状态转移方程中，dp[i][0] 和 dp[i][1] 只会从 dp[i−1][0] 和 dp[i−1][1] 转移而来，因此不必使用数组存储所有的状态，而是使用两个变量 sell 以及 buy 分别表示 dp[..][0] 和 dp[..][1] 直接进行状态转移即可。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)  # 获取价格列表的长度
        sell, buy = 0, -prices[0]  # 初始化卖出和买入的收益，买入收益为负的第一个价格
        
        for i in range(1, n):  # 从第二天开始遍历价格列表
            # 更新卖出的最大收益，取当前不卖出的最大收益和卖出股票后（减去手续费）的最大收益
            sell, buy = max(sell, buy + prices[i] - fee), max(buy, sell - prices[i])
            # 更新买入的最大收益，取当前不买入的最大收益和买入股票后的最大收益
        
        return sell  # 返回最后一天不持有股票的最大收益，即最大利润

用时和内存

时间复杂度：O(n)，其中 n 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。
空间复杂度：O(n) 或 O(1)，取决于是否使用数组存储所有的状态。

方法二、贪心算法
方法一中，将手续费放在卖出时进行计算。如果换一个角度考虑，将手续费放在买入时进行计算，那么就可以得到一种基于贪心的方法。
用 buy 表示在最大化收益的前提下，如果手上拥有一支股票，那么它的最低买入价格是多少。在初始时，buy 的值为 prices[0] 加上手续费 fee。那么当遍历到第 i (i>0) 天时：
如果当前的股票价格 prices[i] 加上手续费 fee 小于 buy，那么与其使用 buy 的价格购买股票，不如以 prices[i]+fee 的价格购买股票，因此将 buy 更新为 prices[i]+fee；
如果当前的股票价格 prices[i] 大于 buy，那么直接卖出股票并且获得 prices[i]−buy 的收益。但实际上，此时卖出股票可能并不是全局最优的（例如下一天股票价格继续上升），因此可以提供一个反悔操作，看成当前手上拥有一支买入价格为 prices[i] 的股票，将 buy 更新为 prices[i]。这样一来，如果下一天股票价格继续上升，会获得 prices[i+1]−prices[i] 的收益，加上这一天 prices[i]−buy 的收益，恰好就等于在这一天不进行任何操作，而在下一天卖出股票的收益；
对于其余的情况，prices[i] 落在区间 [buy−fee,buy] 内，它的价格没有低到放弃手上的股票去选择它，也没有高到可以通过卖出获得收益，因此不进行任何操作。
上面的贪心思想可以浓缩成一句话，即当卖出一支股票时，就立即获得了以相同价格并且免除手续费买入一支股票的权利。在遍历完整个数组 prices 之后之后，就得到了最大的总收益。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)  # 获取价格列表的长度
        buy = prices[0] + fee  # 初始化买入价格，加上手续费
        profit = 0  # 初始化利润为0
        
        for i in range(1, n):  # 从第二天开始遍历价格列表
            if prices[i] + fee < buy:  # 如果当前价格加上手续费比之前的买入价格低，则更新买入价格
                buy = prices[i] + fee
            elif prices[i] > buy:  # 如果当前价格高于买入价格，则卖出并更新利润
                profit += prices[i] - buy
                buy = prices[i]  # 更新买入价格为当前价格，准备下一次交易
        
        return profit  # 返回最终的累计利润

用时和内存

时间复杂度：O(n)，其中 n 为数组的长度。
空间复杂度：O(1)。

第五题、279. 完全平方数

思路

class Solution:
    def numSquares(self, n: int) -> int:
        f = [0] * (n + 1)  # 初始化DP数组，f[i]表示组成i的最少完全平方数的个数

        for i in range(1, n + 1):  # 遍历从1到n的每一个数字
            minn = float('inf')  # 初始化最小值为正无穷大
            for j in range(1, int(i**0.5) + 1):  # 遍历所有可能的完全平方数
                minn = min(minn, f[i - j * j])  # 更新最小值
            f[i] = minn + 1  # 将当前数字i的最小完全平方数个数存入DP数组
        
        return f[n]  # 返回组成n的最少完全平方数的个数

用时和内存

时空复杂度

方法二、数学
此方法数学性较强，结论只做了解

思路

思路

import math

class Solution:
    # 判断是否为完全平方数
    def isPerfectSquare(self, x: int) -> bool:
        y = int(math.sqrt(x))  # 计算x的平方根，并取整
        return y * y == x  # 检查平方根的平方是否等于x

    # 判断是否能表示为 4^k*(8m+7)
    def checkAnswer4(self, x: int) -> bool:
        while x % 4 == 0:  # 逐步除以4，直到不能再被4整除
            x //= 4
        return x % 8 == 7  # 检查结果是否满足 8m+7 的形式

    def numSquares(self, n: int) -> int:
        if self.isPerfectSquare(n):  # 如果n是完全平方数
            return 1  # 直接返回1
        
        if self.checkAnswer4(n):  # 如果n能表示为 4^k*(8m+7)
            return 4  # 根据Lagrange四平方定理，返回4
        
        for i in range(1, int(math.sqrt(n)) + 1):  # 遍历所有小于等于sqrt(n)的完全平方数
            j = n - i * i  # 计算剩余部分
            if self.isPerfectSquare(j):  # 如果剩余部分是完全平方数
                return 2  # 返回2
        
        return 3  # 否则，返回3

用时和内存

时空复杂度

第六题、72.编辑距离

此题的第二个样例复杂，用人脑直观的想也有难度。。
思路看官方题解，较复杂
注意：编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)  # 获取word1的长度
        m = len(word2)  # 获取word2的长度
        
        # 如果其中一个字符串为空串，返回另一个字符串的长度（所有字符都需要删除或插入）
        if n * m == 0:
            return n + m
        
        # 初始化DP数组，D[i][j]表示将word1前i个字符转换为word2前j个字符的最小编辑距离
        D = [[0] * (m + 1) for _ in range(n + 1)]
        
        # 边界状态初始化
        for i in range(n + 1):
            D[i][0] = i  # 将word1的前i个字符转换为空串的编辑距离为i（删除i个字符）
        for j in range(m + 1):
            D[0][j] = j  # 将空串转换为word2的前j个字符的编辑距离为j（插入j个字符）
        
        # 计算所有DP值
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = D[i - 1][j] + 1  # 删除操作
                down = D[i][j - 1] + 1  # 插入操作
                left_down = D[i - 1][j - 1]  # 替换操作（不一定是替换，如果字符相同则不需要加1）
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1  # 如果字符不同，则替换操作需要加1
                D[i][j] = min(left, down, left_down)  # 选择操作数最少的状态
        
        return D[n][m]  # 返回将word1转换为word2的最小编辑距离

用时和内存

时间复杂度 ：O(mn)，其中 m 为 word1 的长度，n 为 word2 的长度。
空间复杂度 ：O(mn)，需要大小为 O(mn) 的 D 数组来记录状态值。

第七题、518.零钱兑换2

注意：此题的基础是完全背包问题
方法、动态规划
这道题中，给定总金额 amount 和数组 coins，要求计算金额之和等于 amount 的硬币组合数。其中，coins 的每个元素可以选取多次，且不考虑选取元素的顺序，因此这道题需要计算的是选取硬币的组合数。
可以通过动态规划的方法计算可能的组合数。用 dp[x] 表示金额之和等于 x 的硬币组合数，目标是求 dp[amount]。
动态规划的边界是 dp[0]=1。只有当不选取任何硬币时，金额之和才为 0，因此只有 1 种硬币组合。
对于面额为 coin 的硬币，当 coin≤i≤amount 时，如果存在一种硬币组合的金额之和等于 i−coin，则在该硬币组合中增加一个面额为 coin 的硬币，即可得到一种金额之和等于 i 的硬币组合。因此需要遍历 coins，对于其中的每一种面额的硬币，更新数组 dp 中的每个大于或等于该面额的元素的值。
由此可以得到动态规划的做法：
初始化 dp[0]=1；
遍历 coins，对于其中的每个元素 coin，进行如下操作：
遍历 i 从 coin 到 amount，将 dp[i−coin] 的值加到 dp[i]。
最终得到 dp[amount] 的值即为答案。
上述做法不会重复计算不同的排列。因为外层循环是遍历数组 coins 的值，内层循环是遍历不同的金额之和，在计算 dp[i] 的值时，可以确保金额之和等于 i 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。
例如，coins=[1,2]，对于 dp[3] 的计算，一定是先遍历硬币面额 1 后遍历硬币面额 2，只会出现以下 2 种组合：
3=1+1+1
3=1+2
硬币面额 2 不可能出现在硬币面额 1 之前，即不会重复计算 3=2+1 的情况。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 初始化DP数组，dp[i]表示组成金额i的不同组合方式的数量
        dp = [0] * (amount + 1)
        dp[0] = 1  # 组成金额0的方式只有一种，即不使用任何硬币
        
        # 遍历每一个硬币
        for coin in coins:
            # 更新DP数组，遍历从当前硬币面额到目标金额
            for i in range(coin, amount + 1):
                # dp[i]的值等于dp[i - coin]的值
                # 表示使用当前硬币coin后的组合方式
                dp[i] += dp[i - coin]
        
        return dp[amount]  # 返回组成目标金额amount的不同组合方式的数量

用时和内存

时间复杂度：O(amount×n)，其中 amount 是总金额，n 是数组 coins 的长度。需要使用数组 coins 中的每个元素遍历并更新数组 dp 中的每个元素的值。
空间复杂度：O(amount)，其中 amount 是总金额。需要创建长度为 amount+1 的数组 dp。