动态规划求解问题的基本特征

1，更优子结构

2，子问题重叠

3，问题存在边界

4，子问题相互独立

母问题的更优解包含其子问题的更优解，我们就称此问题具有更优子结构。即也就是说，子问题更优时，母问题通过优化一定能求得更优解。

子问题本质上是和母问题一样的，只是问题的输入参数不一样，就可以称之为子问题重叠，这是动态规划解决问题的高效的本质所在，我们可以利用很多子问题具有相同的输入参数这一个性质，来减少计算量。

子问题在一定情况下就不存在子问题了， 我们称这种情况为问题存在边界，对于自顶向上和自底向下的 *** ，边界分别是问题的出口和入口。

个子问题在求解更优解时事相互独立的，即本自问题的求解和其他平行子问题是不相干的。当平行子问题解决后，选择权交给母问题时，它才会考虑各子问题之间的关系，是求更大值还是最小值，还是要做相关的运算得到母问题的更优解。