动态规划算法思想和详解
动态规划算法思想和详解
- 动态规划的思想：动态规划的思想是分治，简单来说就是将一个问题分化成一个又一个相同或者相似的小问题，通过得到最小的问题的最优解加上判断条件来得出次小问题的最优解，以此类推最后得出原本问题的最优解。
- 动态规划例题：寻找一条从A所在的层到H所在的层的路径，使得路径值之和最大。
这是一个典型动态规划问题，我们将第0层（A层）到3层（H）层的问题分解成0层到2层，再将0层到2层的问题分解成0层到1层，因为0层到1层是最小问题，所以不可分割。我们首先求0层到1层的最大值问题，再在第一求解的基础上求1层到2层的最大值问题，以此类推，即可求出0层到3层最大值问题。 - 解题步骤：
- 0 - 1层最大值为：A-B = 3；
- 在0 - 1层基础上，1 - 2层最大值为：B-E = 7，则0 - 2层最大值为A-B-E = 3+7=10；
- 在0 - 1层，1 - 2层基础上，2 - 3层最大值为E-G = 8，则0 - 3层最大值为A-B-E-G=10+8=18
- 所以0 - 3层最大值为18。