数据结构与算法 -- 动态规划基础

一、动态规划问题描述

动态规划问题一定具备以下三个特征：

 1、重叠子问题

        在穷举的过程中（比如通过递归），存在重复计算的现象；不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

2、无后效性

        子问题之间的依赖是单向性的，某阶段状态一旦确定，就不受后续决策的影响；无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。

3、最优子结构

        最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。

二、状态转移方程 

1、初始化状态

      由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此我们需要一个“原点”作为计算的开端。 

2、状态参数

        子问题与原问题之间会发生变化的变量就是状态参数， 这个状态在不断逼近初始化状态。而这个不断逼近的过程，叫做状态转移。

3、决策 

        确定了状态，那么什么操作会改变状态，并让它不断逼近初始化状态呢？每当我们挑一枚硬币，用来凑零钱，就会改变状态。在动态规划中，我们将其称之为决策。 

4、备忘录 

        备忘录记录状态转移过程中各状态对应的值。 

三、动态规划适用问题

         动态规划是运筹学上的一种最优化方法。

1、求“最”优解问题

        乘积最大子数组、 最长回文子串、最长上升子序列

2、求可行性

         凑零兑换问题、字符串交错组成问题 

3、求方案总数 

        硬币组合问题、路径规划问题

声明：本文参考极客时间《动态规划面试宝典》