我正在实现一个"；无界背包"-家庭问题。更准确地说，问题是找到一组n硬币(每种硬币的无限数量(的给定数量的所有可能变化。这是leetcode链接，以防万一https://leetcode.com/problems/coin-change-ii/
理论上，两种方法应该具有相同的大-O时间复杂性(O(数量*n((，但它们的表现不同。
本质上，这两种实现因递归树而不同：在一种情况下，它是一个每枚硬币都有分支的树，但正如我所假设的，深度较小(或高度较小(；在第二种情况下，我们有一个二进制递归树，但它更深。这两种实现方式如下。
第一个：
bigO = 0
class Solution:
def dfs(self, amount: int, coins: List[int], starting_from: int) -> int:
global bigO
bigO += 1
if amount < 0 or starting_from == len(coins):
return 0
if amount == 0:
return 1
if self.dp[starting_from][amount] != -1:
return self.dp[starting_from][amount]
all_changes = 0
for i in range(starting_from, len(coins)):
all_changes += self.dfs(amount-coins[i], coins, i)
self.dp[starting_from][amount] = all_changes
return all_changes
def change(self, amount: int, coins: List[int]) -> int:
self.dp = [[-1]*(amount+1) for _ in range(len(coins))]
return self.dfs(amount, coins, 0)
amount = 4000
coins = ... # given below for readability
print(Solution().change(amount, coins)) # outputs 3435
print(bigO) # outputs 24794885
第二个：
class Solution:
def dfs(self, amount: int, coins: List[int], i: int) -> int:
global bigO
bigO += 1
if amount < 0 or i == len(coins):
return 0
if amount == 0:
return 1
if self.dp[i][amount] != -1:
return self.dp[i][amount]
all_changes = self.dfs(amount-coins[i], coins, i) + self.dfs(amount, coins, i+1)
self.dp[i][amount] = all_changes
return all_changes
def change(self, amount: int, coins: List[int]) -> int:
self.dp = [[-1]*(amount+1) for _ in range(len(coins))]
return self.dfs(amount, coins, 0)
amount = 4000
coins = ... # given below for readability
print(Solution().change(amount, coins)) # outputs 3435
print(bigO) # outputs 1143881
注意，我包括"；bigO"；变量来计算方法的实际调用次数。正如你所看到的，我得到的结果相差一个数量级。BTW第一个impl甚至命中"；超过时间限制"；如果你尝试在leetcode上提交它，而第二个就可以了。
有人能解释一下实际表现差异的原因吗？假设两种实现在理论上具有相同的时间复杂性，我是否遗漏了什么？
为了提高问题的可读性，我在下面给出了coins变量值(它必须至少有~200个项目才能产生影响(：
coins = [200,217,234,251,268,285,302,319,336,353,370,387,404,421,438,455,472,489,
506,523,540,557,574,591,608,625,642,659,676,693,710,727,744,761,778,795,812,
829,846,863,880,897,914,931,948,965,982,999,1016,1033,1050,1067,1084,1101,
1118,1135,1152,1169,1186,1203,1220,1237,1254,1271,1288,1305,1322,1339,1356,
1373,1390,1407,1424,1441,1458,1475,1492,1509,1526,1543,1560,1577,1594,1611,
1628,1645,1662,1679,1696,1713,1730,1747,1764,1781,1798,1815,1832,1849,1866,
1883,1900,1917,1934,1951,1968,1985,2002,2019,2036,2053,2070,2087,2104,2121,
2138,2155,2172,2189,2206,2223,2240,2257,2274,2291,2308,2325,2342,2359,2376,
2393,2410,2427,2444,2461,2478,2495,2512,2529,2546,2563,2580,2597,2614,2631,
2648,2665,2682,2699,2716,2733,2750,2767,2784,2801,2818,2835,2852,2869,2886,
2903,2920,2937,2954,2971,2988,3005,3022,3039,3056,3073,3090,3107,3124,3141,
3158,3175,3192,3209,3226,3243,3260,3277,3294,3311,3328,3345,3362,3379,3396,
3413,3430,3447,3464,3481,3498,3515,3532,3549,3566,3583,3600,3617,3634,3651,
3668,3685,3702,3719,3736,3753,3770,3787,3804,3821,3838,3855,3872,3889,3906,
3923,3940,3957,3974,3991,4008,4025,4042,4059,4076,4093,4110,4127,4144,4161,
4178,4195,4212,4229,4246,4263,4280,4297,4314,4331,4348,4365,4382,4399,4416,
4433,4450,4467,4484,4501,4518,4535,4552,4569,4586,4603,4620,4637,4654,4671,
4688,4705,4722,4739,4756,4773,4790,4807,4824,4841,4858,4875,4892,4909,4926,
4943,4960,4977,4994]
感谢Kira在下面的回答，它变得更清晰了，谢谢Kira！
我仍然不明白的是，在第二种情况下，是的，递归树的分支因子较低，但它更深。例如，对于列表[a, b, c]，请注意，使用二进制方法的[c, c, c]组合在第5级，而在第一种情况下，在第3级。列表越长，差异就越大。我画了下面的树：(
第二种情况
root
/
[a] []
/ /
[a, a] [a] [b] []
/ / / /
[a, a, a] [a, a] [a, b] [a] [b, b] [b] [c] []
/
..... [c, c] [c]
/
[c, c, c]
对于第一个：
root
/ |
[a] [b] [c]
/ | | |
[a, a] [a, b] [a, c] [b, b] [b, c] [c, c]
.............. |
[c, c, c]
对于分支因子较低但"深度"较大的第二种情况(就性能而言(与分支因子较大但"深度(较小的第一种情况不可比较，最好的解释是什么？
毕竟，两者都列举了相同数量的给定项目的组合。如果有人帮我理解，我将不胜感激！
理论上应该具有相同big-O时间复杂度(O(数量*n((的两种方法表现不同
这不是真的，因为在第一种情况下，您的DP转换最坏的时间复杂度为O(len(coins((。同时，在第二种情况下，您的DP转换在最坏的情况下只是O(1(。
一般来说，每当计算递归DP的时间复杂性时，最好将记忆参数的范围与过渡状态的时间到复杂性相乘，以获得对整体时间复杂性的良好估计。