我一直对此感到好奇。没有一本书明确说明这一点。
回溯是探索所有的可能性，直到我们发现一种可能性。在这种情况下，我们无法找到可能的解决方案。
据我所知，动态编程的特点是子问题重叠。那么，动态编程是否可以称为使用缓存的回溯（对于以前探索的路径）？
感谢
这是动态编程的一个方面，但它还有更多
举个简单的例子，以斐波那契数为例：
F (n) =
n = 0: 0
n = 1: 1
else: F (n - 2) + F (n - 1)
我们可以将上面的代码称为"回溯"或"递归"。让我们将其转换为"带缓存的回溯"或"带记忆的递归"：
F (n) =
n in Fcache: Fcache[n]
n = 0: 0, and cache it as Fcache[0]
n = 1: 1, and cache it as Fcache[1]
else: F (n - 2) + F (n - 1), and cache it as Fcache[n]
尽管如此，它还有更多
如果一个问题可以通过动态编程来解决，那么就有一个状态和它们之间的依赖关系的有向无环图。有一个国家令我们感兴趣。还有一些基本状态，我们马上就能知道答案。
我们可以遍历该图，从我们感兴趣的顶点到它的所有依赖项，从它们到它们的所有依赖性，等等，在基本状态处停止进一步分支。这可以通过递归来实现。
有向无环图可以看作是顶点上的偏序。我们可以对该图进行拓扑排序，并按排序顺序访问顶点。此外，您可以找到一些简单的总订单，它与您的部分订单一致。
还要注意，我们经常可以观察到状态的一些结构。例如，状态通常可以表示为整数或整数元组。因此，我们可以预先分配一个更容易、更快使用的常规数组，而不是使用通用的缓存技术（例如，关联数组来存储状态->值对）。
回到我们的Fibonacci例子，偏序关系只是状态n >= 2依赖于状态n - 1和n - 2。基本状态为n = 0和n = 1。与这种顺序关系一致的一个简单的总顺序是自然顺序：0、1、2、...。以下是我们的开始：
Preallocate array F with indices 0 to n, inclusive
F[0] = 0
F[1] = 1
好吧，我们有访问各州的顺序。现在，什么是"拜访"？还有两种可能性：
（1） "向后DP"：当我们访问状态u时，我们查看其所有依赖项v，并计算该状态的答案u:
for u = 2, 3, ..., n:
F[u] = F[u - 1] + F[u - 2]
（2） "正向DP"：当我们访问一个状态u时，我们会查看依赖它的所有状态v，并在这些状态中的每一个状态中说明u v:
for u = 1, 2, 3, ..., n - 1:
add F[u] to F[u + 1]
add F[u] to F[u + 2]
注意，在前一种情况下，我们仍然直接使用斐波那契数的公式。然而，在后一种情况下，命令式代码不能很容易地用数学公式表示。尽管如此，在一些问题中，"正向DP"方法更直观（目前没有好的例子；有人愿意贡献它吗？）。
动态规划的另一个用途是很难表示为回溯：Dijkstra的算法也可以被认为是DP。在该算法中，我们通过添加顶点来构造最优路径树。当我们添加一个顶点时，我们使用的事实是，除了路径中的最后一条边之外，它的整个路径都是最优的。因此，我们实际上使用子问题的最优解——这正是我们在DP中所做的事情。不过，我们向树添加顶点的顺序事先还不知道。
编号。或者更确切地说是。
在回溯过程中，你沿着每条路径往下走，然后再往上走。然而，动态编程是自下而上的，所以你只能得到返回的部分，而不是原来的下降部分。此外，动态规划中的顺序更为广度优先，而回溯通常是深度优先。
另一方面，正如您所描述的，内存化（动态编程的近亲）通常与使用缓存的回溯一样工作。
是和否
动态编程基本上是实现递归公式的有效方法，自上而下的DP实际上很多时候都是用递归+缓存完成的：
def f(x):
if x is in cache:
return cache[x]
else:
res <- .. do something with f(x-k)
cahce[x] <- res
return res
注意，自下而上的DP实现方式完全不同，但仍然基本遵循递归方法的基本原理，并在每一步"计算"较小（已知）子问题的递归公式。
然而，为了能够使用DP-你需要有一些问题的特征，主要是-问题的最优解包括其子问题的最优解决方案。它适用的一个例子是最短路径问题（从s到t经过u的最优路径必须由从s到u的最优路径组成）。
它在其他一些问题上不存在，例如顶点覆盖或布尔可满足性问题，因此你不能用DP代替它的回溯解。
编号。您称之为的带有缓存的回溯基本上就是内存化。
在动态编程中，您可以自下而上。也就是说，您从一个不需要任何子问题的地方开始。特别是，当您需要计算第n步时，所有n-1步都已计算完毕。
记忆化的情况并非如此。在这里，您从k步骤（您想要的步骤）开始，并根据需要继续解决前面的步骤。显然，将这些值存储在某个地方，以便以后可以访问这些值。
尽管如此，在内存化和动态编程的情况下，运行时间没有差异。