动态规划

简介

动态规划是一种实用的技巧，它可以用来解决一系列问题。

它的思路很简单，如果你对某个给定的输入解决了一个问题，那么你可以保存已有信息，避免重复计算（重复子问题），节约计算时间。

解决问题的方式

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

一个模型三个特征

什么样的问题适合用动态规划来解决呢？换句话说，动态规划能解决的问题有什么规律可循呢？实际上，动态规划作为一个非常成熟的算法思想，很多人对此已经做了非常全面的总结。我把这部分理论总结为“一个模型三个特征”。

模型

首先，我们来看，什么是“一个模型”？它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模型”。下面我具体来给你讲讲。

我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

两种动态规划解题思路总结

状态转移表法

状态转移表法解题思路大致可以概括为，回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。

状态转移方程法

状态转移方程法的大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。

四种算法思想比较分析

Demo

不同时间段挣钱问题

// 时间段
const times = [
    [1, 4],
    [3, 5],
    [0, 6],
    [4, 7],
    [3, 8],
    [5, 9],
    [6, 10],
    [8, 11],
]

// 时间段对应的价值
const money = [0, 5, 1, 8, 4, 6, 3, 2, 4]

let pres = [0]
for (let i = 0; i < times.length; i++) {
    let pre = 0
    for (let j = i - 1; j >= 0; j--) {
        if (times[i][0] >= times[j][1]) {
            pre = j + 1
            break
        }
    }

    pres.push(pre)
}

let opts = [0]
for (let i = 1; i < 9; i++) {
    // 选择的值
    let s = money[i] + opts[pres[i]]
    // 不选择的值
    let n = opts[i-1]

    // 取最大的
    let v = Math.max(s, n)
    opts[i] = v
}

console.log(opts)

核心方程式： OPT(i) = Max{ OPT(i-1), OPT(pre(i)) + Vi }

斐波那契数列

斐波那契数列需要满足: f(N) = f(N-1) + f(N-2)

前2个数字都是1，需要特殊处理，为了方便运算，声明数组为[0, 1, 1]，这样下标好理解

// 斐波纳切

let arr = [0, 1, 1]

for (let i = 3; i < 20; i++) {
    let v = arr[i-1] + arr[i-2]
    arr[i] = v
}

console.log(arr)