Skip to content

dynamic-programming

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

dynamic-programming

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

Table of Contents generated with DocToc

动态规划

基本思路

References

基本思路：

  1. 判断是否是动态规划问题：
  • 使用动态规划的问题一般都有一些特点可以遵循。例如，求最大/最小值；求可不可行；求方案总数。
  • 大规模问题的答案可以由小规模问题的答案递推得到。即，状态可以转移，例如f[i] = max{f[j] if j < i and …} + 1, f[i][j] = f[i - 1][j] + f[i][j - 1]
  • 子问题的求解思路除了规模之外，没有任何区别。子问题相互独立，即最优子结构。可以从子问题的最优结果推断出更大规模问题的最优结果
  • 如果一个问题是要求出“所有的”方案和结果，则肯定不是使用动态规划
  • 有递归终止条件
  1. 逐步剖析问题：
  • 状态是什么
  • 状态转移方程是什么：当已经知道f(1)~​f(n - 1)的值，然后想办法利用它们求得f(n)
  • 状态的初始值是什么
  • 问题要求的最后答案是什么

问题拆分成子目标：

  1. 建立状态转移方程
  2. 缓存并复用以往结果
  3. 按顺序从小往大算

确认遍历方式：

  1. 遍历的过程中，所需的状态必须是已经计算出来的
  2. 遍历的终点必须是存储结果的那个位置

明确问题（求什么） -> 明确状态（达成解时的状态时什么） -> 明确子问题（状态转移） -> 确认遍历方式（自底向上解决问题，遍历方式依赖于状态转移方向） -> 明确 base case（边界条件）

概念

  1. 求最值
  2. 无后效性
  3. 重叠子问题
  4. 最优子结构
  5. 自底向上

LeetCode

基本的状态转移

动态规划详解（修订版）

动态规划答疑篇

动态规划：不同的定义产生不同的解法

股票系列问题

LeetCode 股票问题的一种通用解法

团灭 LeetCode 股票买卖问题

最基本思路：前一天的决策影响当天决策，经典的 DP 状态转移问题

子序列问题

动态规划设计之最长递增子序列

经典面试题：最长公共子序列

子序列解题模板：最长回文子序列

状态机问题

动态规划之正则表达式

详解一道腾讯面试题：编辑距离

博弈问题

动态规划之博弈问题

背包问题

LeetCode 动态规划专题 5：0-1 背包问题

LeetCode 动态规划专题 6：0-1 背包问题在空间复杂度上的两个优化

LeetCode 动态规划专题 7：面试中的 0-1 背包问题

用背包问题思想来理解硬币找零系列问题

动态规划之背包问题系列

区间 DP

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来由很大的关系。令状态f(i, j)表示将下标位置i到j的所有元素合并能获得的价值的最大值，那么f(i, j) = max(f(i, k) + f(k + 1, j) + cost)，cost为将这两组元素合并起来的代价。

对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

由于计算f(i, j)的值时需要知道所有f(i, k)和f(k + 1, j)的值，而这两个中包含的元素的数量都小于f(i, j)，所以我们以len = j - i + 1作为 DP 的阶段。首先从小到大枚举len，然后枚举i的值，根据len和i用公式计算出j的值，然后枚举在区间[i, j]中枚举k，时间复杂度为O(n^3)

通用公式：

// n 是区间总长度
for (let i = 1; i <= n; i += 1) {
  dp[i][i] = 初始值
}

for (let len = 2; len <= n; len += 1) { // 从小到大枚举区间长度
  for (let i = 1; i <= n - len + 1; i += 1) { // 枚举区间左端点
    let j = i + len - 1 // 根据左端点和区间长度求区间右端点
    if (j > n) break

    dp[i][j] = 极限值

    for(k = i; k < j; k += 1) { // 从区间 [i, j] 中任意位置截断
      // w[i][j] 代表把两堆区间合并所需代价
      // 求最大值则是 Math.max
      dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j])
    }
  }
}

return dp[1][n]

References: