问题如下:
你在玩一个游戏，你开始有n根棍子在一堆(其中n是一个正整数)，每轮你可以从牌堆中拿走1、7或9根木棍(如果少于9根的话)向左，你不能选择那个选项，和7)类似，你想知道最小值达到0棒所需的回合数
我们被要求实现一个朴素的递归解和一个O(n)动态规划解，这是我的答案:
def take(pile, turns, cur):
if cur > pile:
return float("inf")
if cur == pile:
return turns
else:
res = 1 + min(take(pile, turns, cur+1), take(pile, turns,cur+7), take(pile, turns, cur+9))
return res
和DP解
def takeDP(pile, turns, cur):
if cur > pile:
return float("inf")
if mem[cur] != float("inf"):
return mem[cur]
if cur == pile:
return turns
else:
res = 1 + min(takeDP(pile, turns, cur+9), takeDP(pile, turns,cur+7), takeDP(pile, turns, cur+1))
if res < mem[cur]:
mem[cur] = res
return res
当每个计时时，takeDP要快得多，但我正试图弥合理解每个复杂性的差距。我能想到的最好的攻击角度是比较takeDP和take的简化递归树，但我真的无法表达take的O(3^n)是如何优化到O(n)的，足以用语言来证明它。因此，我也不完全相信我的takeDP解决方案是正确的。
请注意以下观察结果，这对两个函数都是正确的:
- 唯一在不同递归调用之间改变的变量是
cur; - 初始
cur等于0; cur永远不能高于n，即堆中木棍的数量。
从上面的观察，您可以得出结论，实际上只有n+1不同的调用:
take(n, 0, 0), take(n, 0, 1), take(n, 0, 2), take(n, 0, 3), ..., take(n, 0, n)
因此，如果总共进行了超过n+1的调用，则必须意味着额外的调用是冗余的，即。，重新计算之前已经计算过的东西。
DP版本确保每次进行新的不同调用时，其返回值存储在数组mem中。如果进行了两个相同的调用，那么第二个调用将立即被if mem[cur] != float("inf"):子句中断。
所以，对于DP版本，最多只能有n+1调用不被if mem[cur] != float("inf"):子句中断。每个n+1调用最多产生3个调用，因此您可以立即得出结论，总共不会超过4n+4调用。事实上，更仔细的分析会说，确实有3n+4调用。但无论如何，即使你只相信不可能有超过4n+4调用，这足以得出结论:DP版本的时间复杂度为O(n).
对于原始递归版本，我们所能说的是，每个递归调用产生3个新的递归调用，直到递归深度为n+1，因此递归调用的总数约为3^n。实际上，每个递归分支的深度都在n和n/9之间，因为cur的增量是1、7或9。因此，我们可以得出结论，朴素递归版本的时间复杂度介于3^n和3^(n/9) ≈ 1.13^n之间。无论如何，即使没有更仔细的分析，这也足以得出这样的结论:单纯递归版本的时间复杂度是指数级的。