动态规划算法基础讲解

"该资源是一份关于动态规划的基础算法讲解的PPT，由杨鑫于2019-08-01制作。内容涵盖了动态规划的起源、基本思想、算法要素以及解题方法，并通过斐波那契数列和兔子繁殖问题为例进行了深入解析。" 动态规划是一种强大的算法，起源于1957年理查德·贝尔曼的研究，它在《Dynamic Programming》一书中被首次提出。贝尔曼同时也提出了著名的Ballman-Ford算法，用于解决包含负权边的最短路径问题，这是对Dijkstra算法的一个补充。 动态规划的核心思想是利用分治策略，但与传统的分治算法有所不同。它不是自顶向下解决问题，而是自底向上，通过解决较小的子问题并存储结果，来构建大问题的解，从而避免了重复计算，提高了效率。动态规划适用的问题需要满足两个关键性质： 1. **最优子结构**：问题的最优解应当包含其子问题的最优解。这意味着找到整个问题的最优解，可以通过找到各个子问题的最优解来构建。 2. **子问题重叠**：在解决问题的过程中，很多子问题是重复出现的。动态规划通过存储这些子问题的结果，减少不必要的计算，提升算法性能。 解决动态规划问题的步骤通常包括： 1. **分析最优解的结构特征**：理解问题的最优解是如何由子问题的最优解组合而成的。 2. **建立最优值的递归关系**：定义递归公式来描述子问题之间的关系。 3. **自底向上计算最优值**：从最小的子问题开始，逐步计算并存储结果，避免重复计算。 4. **构造最优解**：根据存储的子问题最优值，构建原问题的最优解。 以斐波那契数列为示例，其第n项可以通过前两项之和得出。这个关系展示了最优子结构，即每个斐波那契数是其前两个数的和。使用动态规划，我们可以避免重复计算，如计算F(n)时，我们已经知道了F(n-1)和F(n-2)的值。 另一个例子是兔子繁殖问题，模拟“兔子数列”或“兔子问题”。这个问题显示了最优子结构，因为每个月的兔子数是前两个月兔子数的和。通过动态规划，我们可以避免重复计算每个月份的兔子数量，从第一月和第二月开始，逐步计算并记录结果，直到目标月份。 动态规划的难点在于如何准确地提炼出问题的递归关系，这需要对问题有深入的理解。一旦建立了正确的递归公式，动态规划就成为了解决问题的有效工具。