Chapter 1 - 线性动态规划
线性动态规划是什么？
顾名思义，线性动态规划推导问题是线性的，通俗地讲就是逐元素进行推导。拿上期《Prologue - 简述动态规划》 举过的例子（最长递增子序列）来讲，我们可以从两个角度描述线性动态规划
- 状态定义：
dp[n] 是 [0..n] 上问题最优解
- 状态转移：
dp[n] = max(dp[n-1]..dp[0]) + 1
脱离这个例子，将其抽象，即dp[n] = f(dp[n-1]..dp[0])
根据上面的状态定义和状态转移两个方面得知，大规模的问题只与小规模问题的解有关，所以我们解题的过程就是从小到大推导问题的解，这种方式就是线性动态规划。
线性动态规划分类
我们可以将线性动态规划问题分为四类：
- 单串问题（施工中）
- 带维度的单串问题（未完成）
- 双串问题（未完成）
- 矩阵问题（未完成）
下一节，我们将深入单串问题进行探索。
【入门级】初探动态规划 文章被收录于专栏
在这个专栏里，我会参考并简化其他资料，对常见的动态规划题进行类型划分，针对不同类型进行讲解。
投递哈工大机器人集团等公司7个岗位 >
新东方公司福利 1309人发布