在有向无环图中，求出路径的权是构成该路径的有向边的权的和

Answer 1

这里的关键是理解“动态编程”只是指对于某个函数f(x)，对于某些不同的输入x重复执行f会导致不同的结果或执行路径。从这个定义出发，我们可以把缓存看作是动态编程的一个实例。

所以让我们从一个没有动态编程的实现开始。使用回溯，我们可以先执行深度（这在以后会很重要）一组从s开始到T结束的遍历。

let P(a,b) be a path from a->b
let w(p) be the total weight of some path p
let K be the exhaustive set of P(s,t) // a.k.a every path that exists

// Returns Max(p) p  ∈ K
function findMaxPath(G)
    return findMaxPath(s)

// Returns Max(P(n, t))
function findMaxPath(n)
   if (n === t)
      return an empty path // we are already at the target
   declare p = null
   for each e of n // every outgoing edge
     let q = G(n, e)
     let l = findMaxPath(q) // get the maximum path from the neighbor indice to t
     if (l == null) continue
     l = e + l // prepend the outgoing end to the max path of the child node
     if (w(l) > w(p)) p = l // this is most expensive outgoing end that eventually reaches t
   return p // return null if we can't reach t

这个解决方案的问题是它真的很慢。特别是，您最终会重新计算很多路径。以下图为例：

null

let P(a,b) be a path from a->b
let w(p) be the total weight of some path p
let K(n) be the exhaustive set of P(n,t) // a.k.a every path that exists
let C be a cache of Max(w(p)) p ∈ K(n)
// Returns Max(w(p)) p ∈ K(s)
function findMaxPath(G)
    return findMaxPath(s)

// Returns Max(P(n, t))
function findMaxPath(n)
   if exists C[n]
     return C[n] // we already know the most expensive path from n->t
   if (n === t)
      return an empty path // we are already at the target
   declare p = null
   for each e of n // every outgoing edge
     let q = G(n, e)
     let l = findMaxPath(q) // get the maximum path from the neighbor indice to t
     if (l == null) continue
     l = e + l // prepend the outgoing end to the max path of the child node
     if (w(l) > w(p)) p = l // this is most expensive outgoing end that eventually reaches t
   C[n] = p
   return p // return null if we can't reach t