算法学习——动态规划
2022-06-08 本文已影响0人
斐硕人
核心思想
- 自底向上，对应于递归的自上而下
- 状态（数值）转移（一步步）方程（求解）
- 要进行空间优化（减少重复求解次数）
- 使用场景：不要求列出问题的所有解，只要求计算
解的数目或找出其中一个最优解
如果说贪心是局部最优，动态规划就是全局最优
通用解法
- 将问题拆分为子问题
- 什么是子问题：子问题与原问题形式相同或相似，但规模更小
- 限制：子问题求出的解要记录(选择最优情况)，优化子问题求解次数
- 求解：使用状态转移方程
- 确定状态
- 什么是状态：和子问题相关变量的一组取值（为了方便计算存储的数据）
- 怎么存储：是选择一维还是二维数组还是其他数据结构呢
- 分析边界状态
- 状态数组的边界部分（推断已知数据填起始值）
- 确定状态转移方程
- 使用已知的状态（已经存储的数据）求出未知状态（待求解数据）
- 转移过程：类似于递归
- 类似时刻的概念，t0 时刻的值 和 t1 时刻的值
-
根据方程遍历
dp.png
状态转移方程 tips
- 每次只消除一个变量，来寻找状态转移方程
- 若无明显确定的初始状态，可全部初始化为某个一般值，并按照某种排序顺序进行递归遍历更新 ( 感觉像数学题，不会就填 012 )
- 若无法形成递推关系，则考虑状态里的变量是不是少了
使用场景
不要求列出问题的所有解，只要求计算
解的数目或找出其中一个最优解
看到动态规划，我的第一反应是《运筹学》中的动态规划，然而在众多算法讲解下我关注矛盾点逐渐偏移，还好拽回来了。这俩玩意是一个东西，细节略有不同，相关文章3也讲了这个问题。
运筹学中，如果遇到在某个限制条件下求最优解的问题（如背包问题），则可以使用动态规划。基本概念有6个：
- 阶段（问题划分为多个相互联系的时刻）
- 状态（每个阶段问题的状况）
- 决策（当过程处于某阶段的某状态时，可以做出的不同决定，会影响下一阶段状态）
- 策略（决策按顺序排列的集合，要寻找最优策略）
- 状态转移方程（一个状态到另一个状态的演变过程）
- 指标函数和最优值函数（指标函数：衡量过程优劣的数量指标，如各阶段指标的
和或者乘积，最优值函数：指标函数的最优值，min或max）
其强调了策略的概念，结合该点能更快的识别动态规划问题。
相关文章
