动态规划法

动态规划法

一、动态规划法的设计思想

  动态规划是一种解决多阶段决策问题的优化方法，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

1、数塔问题：多阶段决策问题

  从数塔的顶层出发，在每个节点都可以选择向左走或者向右走，一直走到最底层.
要求找出一条路径，是的路径上的数值和最大。

  想办法转化成单阶段问题：从顶层塔顶8开始走，要求五层塔的最优值，则可以转化成下面两个四层塔的最优值

动态规划法所能解决的问题一般具有以下三个特征：

  最优性原理：如果问题的最优解所能包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优性原理。

  无后效性：即某阶段状态一旦确定，就不受这个状态以后的决策影响，也就是说，某状态以后的过程不会影响以前的状态，只与当前的状态有关。

  有重叠子问题：即子问题之间不是独立的，一个子问题在下一阶段的决策中可能被多次使用到。

动态规划法的求解过程：

  规划子问题：分析最优解的性质，并刻画其结构特征，将原问题分解为若干个子问题，每个子问题对应一个决策阶段，并且子问题之间具有重叠关系。（简单来说就是把大问题划分成多个小问题）

  确定动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式（即动态规划函数），递归的定义最优解。

  求解所有子问题：设计表格，以自底向上或者自顶向下的记忆化方式计算各个问题的最优值并填表，实现动态规划过程。

  构造问题的最优解：根据计算所有子问题最优值时得到的信息构造最优解。