什么是动态规划？
5
动态规划是将过去的知识用来简化未来问题的解决方法。
一个很好的例子是求解斐波那契数列, 当n=1,000,002时。这将是一个非常漫长的过程，但如果我告诉你n=1,000,000和n=1,000,001的结果呢？问题突然变得更加容易处理了。
动态规划在字符串问题中经常被使用，比如字符串编辑问题。你先解决一部分子问题，然后利用这些信息来解决更复杂的原始问题。
使用动态规划时，通常会将结果存储在某种表格中。当你需要问题的答案时，你可以查询表格，看看是否已经知道它是什么。如果没有，您可以使用表格中的数据为自己提供达到答案所需的步骤。
Cormen算法书有一章关于动态规划的描述，而且它在Google Books上是免费的！点击这里查看。
10
动态规划是一种技术，用于避免在递归算法中多次计算相同的子问题。
让我们以斐波那契数列为例：找到由以下公式定义的第n个斐波那契数：
Fn = Fn-1 + Fn-2 并且 F0 = 0，F1 = 1
递归
显而易见的方法是使用递归：
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
动态规划
- 自顶向下 - 记忆化搜索
递归会进行许多不必要的计算，因为给定的斐波那契数会被多次计算。改进这种情况的简单方法是缓存结果：
cache = {}
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
if n in cache:
return cache[n]
cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
return cache[n]
- 自下而上
更好的方法是通过按正确顺序评估结果来完全摆脱递归：
cache = {}
def fibonacci(n):
cache[0] = 0
cache[1] = 1
for i in range(2, n + 1):
cache[i] = cache[i - 1] + cache[i - 2]
return cache[n]
我们甚至可以使用常量空间，只存储沿途必要的部分结果：
def fibonacci(n):
fi_minus_2 = 0
fi_minus_1 = 1
for i in range(2, n + 1):
fi = fi_minus_1 + fi_minus_2
fi_minus_1, fi_minus_2 = fi, fi_minus_1
return fi
如何应用动态规划？
- 在问题中找到递归。
- 自顶向下：将每个子问题的答案存储在表中，以避免重新计算它们。
- 自底向上：找到正确的顺序以评估结果，以便在需要时可用部分结果。
动态规划通常适用于具有固有从左到右顺序的问题，例如字符串、树或整数序列。如果朴素递归算法不会多次计算相同的子问题，则动态规划无法发挥作用。
我制作了一个问题集以帮助理解这种逻辑：https://github.com/tristanguigue/dynamic-programing
4
if n in cache，就像从上往下的例子一样，还是我漏掉了什么？ - DavidC记忆化是指存储函数调用的先前结果（真正的函数在给定相同的输入时总是返回相同的内容）。 在结果存储之前，它对算法复杂度没有影响。
递归是一种函数调用自身的方法，通常使用较小的数据集。 由于大多数递归函数可以转换为类似的迭代函数，因此这对算法复杂度也没有影响。
动态规划是解决更易解决的子问题并从中构建答案的过程。 大多数 DP 算法的运行时间将介于贪心算法（如果存在）和指数算法之间（枚举所有可能性并找到最佳解）。
- DP 算法可以使用递归实现，但不必如此。
- DP 算法无法通过记忆化加速，因为每个子问题只会被解决一次（或“solve”函数只会被调用一次）。
1
这是一种优化算法，可以缩短运行时间。
虽然贪心算法通常被称为“天真”，因为它可能在同一组数据上运行多次，但动态规划通过更深入地理解必须存储的部分结果来避免这种问题，以帮助构建最终解决方案。
一个简单的例子是只通过会对解决方案做出贡献的节点遍历树或图，或将迄今为止找到的解决方案放入表格中，以便避免重复遍历相同的节点。
以下是一个适用于动态规划的问题示例，来自UVA的在线评测：Edit Steps Ladder.
我将简要介绍这个问题分析的重要部分，取自书籍Programming Challenges，建议您查看一下。
这里，对于收集最优部分结果所需的非常特殊的分析，是使解决方案成为“动态”的关键。 这里 是同一问题的另一种完整解决方案。尽管其执行方式不同，但它也是“动态”的。建议您通过将其提交给UVA的在线评测器来检查解决方案的效率。我发现如此繁重的问题如何被高效地解决令人惊讶。Take a good look at that problem, if we define a cost function telling us how far appart two strings are, we have two consider the three natural types of changes:
Substitution - change a single character from pattern "s" to a different character in text "t", such as changing "shot" to "spot".
Insertion - insert a single character into pattern "s" to help it match text "t", such as changing "ago" to "agog".
Deletion - delete a single character from pattern "s" to help it match text "t", such as changing "hour" to "our".
When we set each of this operations to cost one step we define the edit distance between two strings. So how do we compute it?
We can define a recursive algorithm using the observation that the last character in the string must be either matched, substituted, inserted or deleted. Chopping off the characters in the last edit operation leaves a pair operation leaves a pair of smaller strings. Let i and j be the last character of the relevant prefix of and t, respectively. there are three pairs of shorter strings after the last operation, corresponding to the string after a match/substitution, insertion or deletion. If we knew the cost of editing the three pairs of smaller strings, we could decide which option leads to the best solution and choose that option accordingly. We can learn this cost, through the awesome thing that's recursion:
#define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ int string_compare(char *s, char *t, int i, int j) { int k; /* counter */ int opt[3]; /* cost of the three options */ int lowest_cost; /* lowest cost */ if (i == 0) return(j * indel(’ ’)); if (j == 0) return(i * indel(’ ’)); opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]); opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]); opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]); lowest_cost = opt[MATCH]; for (k=INSERT; k<=DELETE; k++) if (opt[k] < lowest_cost) lowest_cost = opt[k]; return( lowest_cost ); }This algorithm is correct, but is also impossibly slow.
Running on our computer, it takes several seconds to compare two 11-character strings, and the computation disappears into never-never land on anything longer.
Why is the algorithm so slow? It takes exponential time because it recomputes values again and again and again. At every position in the string, the recursion branches three ways, meaning it grows at a rate of at least 3^n – indeed, even faster since most of the calls reduce only one of the two indices, not both of them.
So how can we make the algorithm practical? The important observation is that most of these recursive calls are computing things that have already been computed before. How do we know? Well, there can only be |s| · |t| possible unique recursive calls, since there are only that many distinct (i, j) pairs to serve as the parameters of recursive calls.
By storing the values for each of these (i, j) pairs in a table, we can avoid recomputing them and just look them up as needed.
The table is a two-dimensional matrix m where each of the |s|·|t| cells contains the cost of the optimal solution of this subproblem, as well as a parent pointer explaining how we got to this location:
typedef struct { int cost; /* cost of reaching this cell */ int parent; /* parent cell */ } cell; cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */The dynamic programming version has three differences from the recursive version.
First, it gets its intermediate values using table lookup instead of recursive calls.
**Second,**it updates the parent field of each cell, which will enable us to reconstruct the edit sequence later.
**Third,**Third, it is instrumented using a more general goal
cell()function instead of just returning m[|s|][|t|].cost. This will enable us to apply this routine to a wider class of problems.
2
更详细地讲，要解决最短路径问题，您需要：
- 找到从起始节点到每个接触节点的距离（例如从A到B和C） - 找到那些节点到接触它们的节点的距离（从B到D和E，从C到E和F） - 现在我们知道了从A到E的最短路径：它是我们已经访问过的某个节点x的A-x和x-E的最短和 - 重复此过程直到到达最终目标节点
因为我们是自下而上地工作，所以在使用子问题的解时，我们已经拥有了这些解，通过记忆化它们。
请记住，动态规划问题必须具有重叠子问题和最优子结构。生成斐波那契数列不是动态规划问题；它利用了备忘录技术，因为它具有重叠子问题，但它没有最优子结构（因为没有涉及到优化问题）。
动态规划
定义
动态规划（DP）是一种解决具有重叠子问题的问题的通用算法设计技术。这种技术是由美国数学家“理查德·贝尔曼”在1950年代发明的。
关键思想
关键思想是保存重叠较小子问题的答案，以避免重新计算。
动态规划属性
- 一个实例使用较小实例的解来解决。
- 较小实例的解可能需要多次使用，因此将它们的结果存储在表中。
- 因此，每个较小的实例只被解决一次。
- 额外的空间被用来节省时间。
我对动态规划（一种特定问题的强大算法）也非常陌生。
简单来说，就将动态规划视为使用“先前知识”的递归方法。
在这里，“先前知识”是最重要的，要记录已经解决的子问题的解决方案。
考虑维基百科上关于dp的最基本的例子，求解斐波那契数列。
function fib(n) // naive implementation
if n <=1 return n
return fib(n − 1) + fib(n − 2)
让我们拆解函数调用，假设 n = 5
fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
特别地，fib(2) 从头计算了三次。在更大的例子中，许多 fib 的值或子问题都会被重新计算，导致指数时间算法。
现在，让我们尝试通过将已经找到的值存储在数据结构中，比如一个 Map。
var m := map(0 → 0, 1 → 1)
function fib(n)
if key n is not in map m
m[n] := fib(n − 1) + fib(n − 2)
return m[n]
在这里，我们将子问题的解决方案保存在映射中，如果我们还没有它。这种保存已经计算过的值的技术称为记忆化。
最后，对于一个问题，首先尝试找到状态（可能的子问题），并尝试考虑更好的递归方法，以便您可以将先前子问题的解决方案用于进一步的子问题。
1
动态规划算法的七个步骤如下：
1.确定一个递归属性，给出问题实例的解。 2.按照递归属性开发递归算法。 3.查看是否在递归调用中多次解决同一个问题实例。 4.开发备忘录式递归算法。 5.查看在内存中存储数据的模式。 6.将备忘录式递归算法转换为迭代算法。 7.使用所需的存储空间进行存储优化，以优化迭代算法。
3
动态规划正如其名，使用先前计算的值来动态构建下一个新解决方案。
动态规划的应用场景：如果您的解决方案基于最优子结构和重叠子问题，那么使用先前计算的值将有所帮助，以免必须重新计算。这是自下而上的方法。例如，如果需要计算fib(n)，则只需添加先前计算的fib(n-1)和fib(n-2)的值即可。
递归：基本上将问题细分为较小的部分以便更容易解决，但请注意它不能避免在其他递归调用中已经计算过相同的值而导致重新计算。
记忆化：基本上是将旧的递归计算值存储在表中，这样将避免重新计算，如果某个先前调用已经计算过该值，则任何值仅计算一次。因此，在计算之前，我们检查是否已经计算了该值，如果已计算，则从表中返回相同的值，而不是重新计算。这也是自上而下的方法。
这里是一个简单的Python代码示例，演示了Fibonacci数列的递归，自顶向下和自底向上方法：
递归：O(2n)
def fib_recursive(n):
if n == 1 or n == 2:
return 1
else:
return fib_recursive(n-1) + fib_recursive(n-2)
print(fib_recursive(40))
自顶向下：O(n) 适用于更大的输入
def fib_memoize_or_top_down(n, mem):
if mem[n] is not 0:
return mem[n]
else:
mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
return mem[n]
n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))
自底向上：O(n) 适用于简单和小输入大小
def fib_bottom_up(n):
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
if n == 1 or n == 2:
return 1
for i in range(3, n+1):
mem[i] = mem[i-1] + mem[i-2]
return mem[n]
print(fib_bottom_up(40))
原文链接
- 相关问题
- 8 动态规划
- 4 加油站动态规划
- 5 动态规划问题
- 9 动态规划问题
- 5 接近动态规划
- 358 什么是记忆化和动态规划的区别？
- 5 “动态规划”和“普通”编程有什么不同？
- 7 计数问题 - 动态规划
- 5 动态规划求和
- 11 金字塔动态规划