台大资讯之芽视频之动态规划系列

https://www.youtube.com/watch?v=J3oLkc_TEVw

Q: 动态规划方法
动态规划方法是把当前一段和未来的一段分开，又把当前效益和未来的效益结合起来考虑的一种最优化方法，因此每段决策的选择都是从全局来考虑的，与该段的最优选择答案一般是不同的。
一般来说，能够采用动态规划方法求解的问题必须满足.最优化原理和.无后效性原则。

Q: 最优化原理
作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的的状态而言，余下的决策序列必然成最优子策略。也就是一个最优策略的子策略也是最优的。 子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。

Q: 无后效性==马儿可夫性
所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。具体地说，如果一个问题被划分各个阶段之后，阶段 I 中的状态只能由阶段 I+1 中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系，这就是无后效性。

Q: 大致思想？
提取信息的共性，将影响到今后状态决策的信息提取出来，信息提取的思路可以从搜索开始，寻找一个合适的顺序去求得每个状态，弱化阶段的概念。动态规划可以看出是对搜索的一种记忆优化，尽量使搜索的状态保持的信息尽可能的精简—就是搜索的总状态越少越好，和搜索不同的是按照某种特定的顺序。
寻找合适的顺序，第一种是按照什么样的顺序求出每个状态的值，第二种是按照什么样的顺序进行状态转移，或者说状态转移方程的书写。
顺推思想
倒推思想

Q: 转移状态优化
矩阵快速幂优化
状态压缩 bit