乐趣区

关于dynamic-programming:Y-分钟速成-Dynamic-Programming

jiezi

源代码下载：dynamic-programming-cn.html.markdown

动静布局

简介

动静布局是一种实用的技巧，它能够用来解决一系列特定问题。它的思路很简略，如果你对某个给定的输出解决了一个问题，那么你能够保留已有信息，以防止反复计算，节约计算工夫。

记住，如果遗记历史，就要被迫做更多的苦力。斐波那契数列就是一个显然的例子。

解决问题的形式

  1. 自顶向下 : 利用分支策略合成问题。如果你曾经解决过以后子问题了，那么就返回已有信息。如果以后子问题没有计算过，那么就对它进行计算。这样的办法很易于思考、很直观。这被称作“记忆化”。
  2. 自底向上 : 首先剖析问题，将问题合成为不同规模的问题，并决定它们的程序，按程序计算，直到解决给定规模的问题。这样的流程能够保障在解决较大的问题之前解决（它所依赖的）较小的问题。这种流程被称作“动静布局”。

动静布局的例子最长回升子序列问题。给定 S = {a[1] , a[2] , a[3], a[4], …………., a[n-1], a[n] }，求出一个子序列，使得对于所有在这个子序列中所有满足 j <i 的 j 与 i，满足 aj<ai。首先咱们要探讨以原序列的第 i 个元素结尾的最长回升子序列 dp[i]。那么答案是整个 dp 序列的最大值。思考 dp[i]，它的最初一个元素为 a[i]。枚举它的倒数第二个元素 a[j]，则 a[j]<a[i]成立。则 dp[i]就是所有这样的 dp[j]的最大值加上 1(最初一个元素)。这个算法具备 O(n^2)的工夫复杂度。

此算法的伪代码：

for i=0 to n-1
    dp[i]=0
    for j=0 to i-1
        if (a[i] >  a[j] and dp[i]<dp[j])
            LS[i] = LS[j]
    dp[i]=dp[i]+1
for i=0 to n-1
    if (largest < dp[i])
        largest = dp[i]

这个算法的复杂度能够通过将数组换为其余数据结构来优化，来取得 O(n * log n)的工夫复杂度。

同样的思路能够求出有向无环图上的最大门路。

一些驰名的动静布局问题及其实现

Floyd Warshall 算法 – 教程与 C 实现源码
整数背包问题 – 教程与 C 实现源码
最长公共子序列问题 – 教程与 C 实现源码

在线资源

  • codechef
  • 洛谷

有倡议？或者发现什么谬误？在 Github 上开一个 issue，或者发动 pull request！

原文由 Akashdeep Goel 编写，并由 0 个好心人批改。
Translated by: EtaoinWu
© 2022 Akashdeep Goel
本作品采纳 CC BY-SA 3.0 协定进行许可。

退出移动版