sam*_*moz 202
动态编程是指您使用过去的知识来更轻松地解决未来问题.
一个很好的例子是解决n = 1,000,002的Fibonacci序列.
这将是一个非常漫长的过程,但如果我给你n = 1,000,000和n = 1,000,001的结果怎么办？突然间问题变得更易于管理.
动态编程在字符串问题中经常使用,例如字符串编辑问题.您解决了问题的一个子集,然后使用该信息来解决更难的原始问题.
通过动态编程,您可以将结果存储在某种表格中.当您需要问题的答案时,您可以参考该表,看看您是否已经知道它是什么.如果没有,您可以使用表格中的数据为自己提供迈向答案的垫脚石.
Cormen算法书有一个关于动态编程的伟大章节.它在谷歌图书上是免费的!检查它在这里.
Tri*_*tan 159
动态编程是一种用于避免在递归算法中多次计算相同子问题的技术.
让我们来看一下斐波那契数的简单例子:找到由第 i 个定义的第 n 个斐波那契数
F n = F n-1 + F n-2且F 0 = 0,F 1 = 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
小智 37
Memoization是存储函数调用的先前结果的时候(实际函数总是返回相同的东西,给定相同的输入).在存储结果之前,它对算法复杂性没有影响.
递归是调用自身的函数的方法,通常使用较小的数据集.由于大多数递归函数可以转换为类似的迭代函数,因此这也不会对算法复杂性产生影响.
动态编程是解决更容易解决的子问题并从中解决问题的过程.大多数DP算法将处于贪婪算法(如果存在)和指数(枚举所有可能性并找到最佳可能性)算法之间的运行时间.
and*_*and 20
这是算法的优化,可以缩短运行时间.
虽然贪婪算法通常被称为天真,因为它可能在同一组数据上运行多次,但动态编程通过更深入地理解必须存储的部分结果来帮助构建最终解决方案,从而避免了这一陷阱.
一个简单的例子是仅通过可以提供解决方案的节点遍历树或图,或者将您到目前为止找到的解决方案放入表中,这样您就可以避免反复遍历相同的节点.
以下是一个适用于动态编程的问题示例,来自UVA的在线评判:编辑步骤梯形图.
我将快速介绍这个问题分析的重要部分,摘自编程挑战,我建议你看一下.
仔细看看这个问题,如果我们定义一个成本函数告诉我们appart两个字符串有多远,我们有两个考虑三种自然类型的变化:
替换 - 将单个字符从模式"s"更改为文本"t"中的不同字符,例如将"shot"更改为"spot".
插入 - 将单个字符插入到模式"s"中以帮助它匹配文本"t",例如将"之前"更改为"agog".
删除 - 从模式"s"中删除单个字符以帮助它匹配文本"t",例如将"hour"更改为"our".
当我们将每个操作设置为一步时,我们定义两个字符串之间的编辑距离.那么我们如何计算呢？
我们可以使用观察来定义递归算法,即字符串中的最后一个字符必须匹配,替换,插入或删除.在最后一次编辑操作中删除字符会使一对操作留下一对较小的字符串.设i和j分别是相关前缀和t的最后一个字符.最后一次操作后有三对较短的字符串,对应于匹配/替换,插入或删除后的字符串.如果我们知道编辑三对较小字符串的成本,我们可以决定哪个选项可以获得最佳解决方案并相应地选择该选项.我们可以通过递归的令人敬畏的事情来学习这个成本:
#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 );
}
这个算法是正确的,但也 很慢.
在我们的计算机上运行,比较两个11个字符的字符串需要花费几秒钟的时间,并且计算消失后永远不会落在任何更长的字符串上.
为什么算法这么慢？它需要指数时间,因为它会一次又一次地重新计算值.在字符串中的每个位置,递归分支三种方式,这意味着它以至少3 ^ n的速率增长 - 实际上甚至更快,因为大多数调用仅减少两个索引中的一个,而不是两个.
那么我们如何才能使算法实用呢？重要的观察结果是,大多数这些递归调用都是计算之前已经计算过的东西.我们怎么知道？好吧,只能有| s | ·| t | 可能的唯一递归调用,因为只有很多不同的(i,j)对作为递归调用的参数.
通过将这些(i,j)对中的每一对的值存储在表中,我们可以避免重新计算它们,并根据需要查看它们.
该表是二维矩阵m,其中每个| s |·| t | 单元格包含此子问题的最优解的成本,以及解释我们如何到达此位置的父指针:
Run Code Online (Sandbox Code Playgroud)typedef struct { int cost; /* cost of reaching this cell */ int parent; /* parent cell */ } cell; cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */动态编程版本与递归版本有三个不同之处.
首先,它使用表查找而不是递归调用来获取其中间值.
**其次,**它更新每个单元格的父字段,这将使我们以后能够重建编辑序列.
**第三,**第三,它使用更通用的目标cell()函数进行检测,而不仅仅返回m [| s |] [| t |] .cost.这将使我们能够将此例程应用于更广泛的问题.
在这里,对收集最佳部分结果所需要的非常具体的分析是使解决方案成为"动态"解决方案的原因.
这是针对同一问题的替代完整解决方案.即使它的执行不同,它也是一个"动态"的.我建议您通过将其提交给UVA的在线评委来了解解决方案的效率.我觉得如此有效地处理这么重的问题是多么惊人.
Nic*_*wis 11
动态编程的关键部分是"重叠子问题"和"最优子结构".问题的这些属性意味着最优解决方案由其子问题的最优解决方案组成.例如,最短路径问题表现出最佳子结构.从A到C的最短路径是从A到某个节点B的最短路径,接着是从该节点B到C的最短路径.
更详细地说,要解决最短路径问题,您将:
因为我们正在自下而上地工作,所以我们已经通过记忆它们来解决子问题.
请记住,动态编程问题必须具有重叠的子问题和最佳子结构.生成Fibonacci序列不是动态编程问题; 它利用了memoization,因为它有重叠的子问题,但它没有最佳的子结构(因为没有涉及优化问题).
我对动态规划（针对特定类型问题的强大算法）也很陌生
用最简单的话说，只需将动态规划视为使用先前知识的递归方法
以前的知识在这里最重要，跟踪您已经拥有的子问题的解决方案。
考虑一下，维基百科中 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) 从头开始计算了 3 次。在较大的示例中，会重新计算更多 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]
在这里，我们将在地图中保存子问题的解决方案，如果我们还没有的话。这种保存我们已经计算过的值的技术被称为记忆化。
最后，对于一个问题，首先尝试找到状态（可能的子问题并尝试考虑更好的递归方法，以便您可以将先前子问题的解决方案用于进一步的子问题）。
动态规划是一种解决具有重叠子问题的技术。动态规划算法只解决每个子问题一次，然后将其答案保存在表（数组）中。避免每次遇到子问题时重新计算答案的工作。动态规划的基本思想是：避免计算相同的东西两次，通常是通过保留子问题的已知结果表。
动态规划算法开发的七个步骤如下：
动态编程
定义
动态编程(DP)是一种通用的算法设计技术,用于解决重叠子问题.这种技术是美国数学家"理查德贝尔曼"在20世纪50年代发明的.
关键理念
关键的想法是保存重叠较小的子问题的答案,以避免重新计算.
动态编程属性