线性动态规划是什么？

  顾名思义，线性动态规划推导问题是线性的，通俗地讲就是逐元素进行推导。拿上期《Prologue - 简述动态规划》 举过的例子（最长递增子序列）来讲，我们可以从两个角度描述线性动态规划

  • 状态定义：
    dp[n] 是 [0..n] 上问题最优解
  • 状态转移：
    dp[n] = max(dp[n-1]..dp[0]) + 1
    脱离这个例子，将其抽象，即
    dp[n] = f(dp[n-1]..dp[0])

  根据上面的状态定义和状态转移两个方面得知，大规模的问题只与小规模问题的解有关，所以我们解题的过程就是从小到大推导问题的解，这种方式就是线性动态规划。

线性动态规划分类

  我们可以将线性动态规划问题分为四类：

  1. 单串问题（施工中）
  2. 带维度的单串问题（未完成）
  3. 双串问题（未完成）
  4. 矩阵问题（未完成）

  下一节，我们将深入单串问题进行探索。