动态规划-Python学习

1、什么是动态规划

动态规划通常用于数学、计算机、经济学中，把原问题分解为相对简单的子问题的方式来求解复杂问题。通过拆分问题，定义问题状态和状态之间的关系，使问题能够用递推的方式去解决。

动态规划可以有效的解决子问题重叠的问题，它会将子问题的解存储在列表中，避免了不必要的重复计算。

2、基本策略

动态规划主要方法就是将待求解的问题分成若干子问题或者子阶段，按顺序求解子阶段，前一阶段的解为后一阶段提供有用信息。求解子问题时列出各种可能解，通过决策来保留可以达到最优解的局部解。由于子问题经常重叠，在求解时多个子问题可能被重复调用，但是通过填表的方式很好地避免了重复计算。

3、适用问题

适合动态规划的问题具有三个特点：最优化原理、无后效性、有重叠子问题

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

无后效性：某个阶段状态确定后，后续的决策不影响这个状态，这个状态只与当前状态有关。

有重叠子问题：子问题间不独立，在下一阶段决策中可能多次被用到。虽然这不是动态规划的必要条件，但是没有这个性质动态规划相对其他算法就没有优势了。

4、求解步骤

初始状态--决策1--决策2--...--决策n--结束

第一步：划分阶段，注意需要是有序获可排序的。

第二步：确定状态间的变量，客观的表现出各阶段的不同的情况。注意状态选择需要满足无后续性。

第三步：确定决策及状态转移方程，根据相邻的两个状态来确定决策方法及转移方程。

第四步：边界条件，状态转移方程需要有个递推终止的条件。

5、算法实现

动态规划三要素：

问题阶段

每个阶段的状态

相邻状态的递推关系

通过一个二维表来描述，行代表决策阶段，列代表问题状态，表格需要填写每个阶段每个状态下的最优解，根据递推关系，最终得到问题的最优解。