python - 阶乘的迭代动态规划效果很好，但它违反了 dp 的定义，因为阶乘中没有重叠的子问题

Question

我对根据 dp 的定义的动态规划有疑问，如果问题具有最优子结构并且重叠一些问题，则可以使用 dp 解决，但在阶乘问题中，所有子问题都是唯一的，但如果我们应用迭代 dp，我们仍然得到正确答案为什么会这样？？？如果我错了，请纠正我

def fact(n):
  dp =  [-1 for i in range(n+1)]
  dp[0] = 1
  dp[1] = 1
  i = 2
  while i <= n:
    dp[i] = i*dp[i-1]
    i+=1
  return dp[n]
n = int(input())
ans = fact(n)
print(ans)

标签： pythondata-structures

Answer 1

动态规划有两种方法：自顶向下和自底向上。

• 自上而下：您从顶部构建，这是所有重叠子问题都清晰可见的地方（递归）。
• 自下而上：您从底部构建。您找到了基本案例的答案，并将您的解决方案构建到顶部，这就是您所做的。重叠的子问题在这里不太明显。