动态规划 dynamic programming


定义

https://en.wikipedia.org/wiki/Dynamic_programming
https://zh.wikipedia.org/wiki/动态规划

  • "Simplifying a complicated problem by breaking it down into simpler subproblems"(in a recursive manager)
  • Divide & Conquer + Optimal substructure (分治+最优子结构)

DP 顺推模板

function DP():
dp = [][] # 二维情况
for i = 0 .. M { for j = 0 .. N {
  dp[i][j] = _Function(dp[i’][j’]...) }
}
return dp[M][N];

关键点

动态规划和递归或者分治 没有根本上的区别 (关键看有无最优的子结构)
共性: 找到重复子问题
差异性: 最优子结构、中途可以淘汰次优解

自底向上

转化递归为 递推

动态规划关键点

  1. 最优子结构 opt[n] = best_of(opt[n-1]+ opt[n-2], ...)
  2. 存储中间状态 opt[i]
  3. 递推公式 (状态转移方程或者 DP方程)

    fib: opt[i] = opt[n-1]+opt[n-2] 二维路径: opt[i,j] = opt[i+1][j]+opt[i][j+1] (且判断 a[i,j] 是否是空地)

感触

  1. 人肉递归低效、很累
  2. 找到最近最简方法,将其拆解成可重复解决的问题
  3. 数学归纳法思维(抵制人肉递归的诱惑)

动态规划小结

  1. 打破自己的思维惯性,形成机器思维
  2. 理解复杂逻辑的关键
  3. 也是职业进阶的要点要领

3 步 DP

问题抽象化,定义成状态,套用模版,写出嵌套循环,写DP方程

  1. 子问题
  2. 状态空间
  3. DP 方程

MIT 5 步 DP

MIT课程】动态规划 I - 最短路径算法(已添加字幕)

  1. 定义子问题
  2. 猜递推方程
  3. 合并子问题的解
  4. 递归 & 记忆化搜索 or 建立 DP 状态表(DP table) 自底向上递推
  5. 得到原问题的解

leetcode

62.不同路径
63.不同路径 II
70. 爬楼梯
1143.最长公共子序列
120. 三角形最小路径和
53. 最大子序和