Chapter 1 - 线性动态规划

线性动态规划是什么？

  顾名思义，线性动态规划推导问题是线性的，通俗地讲就是逐元素进行推导。拿上期《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. 矩阵问题（未完成）

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