DP入门（c++）_c++ dp

动态规划

在学习动态规划之前，

我们必须要先掌握记忆化搜索和递推，这两块东西搞好了之后，面对动态规划那就容易多啦！

动态规划（英语：Dynamic programming，简称 DP），

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

（是不是很像前面讲解过的一种算法——分治，其实可以认为动态规划就是特殊的分治）

动态规划常常适用于有无后效性和最优子结构性质的问题，

并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于暴力递归解法。

使用动态规划解决的问题有个明显的特点，

一旦一个子问题的求解得到结果，

以后的计算过程就不会修改它，这样的特点叫做无后效性，

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化搜索，

自底向上就是递推。

做题方法

(1)划分阶段：

按照问题的时间或空间特征，把问题分为若干个阶段。

在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

   (2)确定状态和状态变量：

将问题发展到各个阶段时所处于的各种客观情况用不同的状态表