动态规划
摘要
- 动态规划的解题步骤
- 动态规划的空间优化技巧——滚动数组
- 坐标型动态规划的分支——接龙型动态规划
- 通过经典 DP 题 LIS 看动态规划如何记录具体方案
- 上下左右都可以走的矩阵如何进行动态规划
为什么难?
是一种哲学思想，而不是很具体的算法
每个子类型都是一个新的算法
学习周期很长，一月入门，两月上手
动态规划的解题步骤
- 判断是否能够使用动态规划算法
- 判断动态规划的题型
- 使用动规四要素进行解题
动态规划的题型
- 坐标
- 一维坐标
- 二维坐标
- 前缀性
- 一个字符串划分 — 划分型
- 两个字符串匹配 — 匹配型
- 背包型
- 最常考
- 区间型
- 考较少
- 博弈型
- 考得少
- 树型
- 基本不考
- 状态压缩型
- TSP 问题（作为加分项）
- 其他基本不考
动规四要素
- 状态 State
- 坐标
- 前缀
- 区间
- …
- 方程 Function
- 上一步从哪儿来
- 如何依赖更小规模的问题
- max/min/sum/or
- 初始化 Initialization
- 第 0 行第 0 列
- 起点是啥
- 答案 Answer
- 终点在哪儿
动态规划的时间复杂度
O (状态总数 * 每个状态的处理耗费) = O (状态总数 * 决策数)
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。