本文主要是介绍讨论动态规划的优点 - 相比于穷举法 - （以最短路径为例），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
讨论动态规划的优点 - 相比于穷举法 - （以最短路径为例）
一、熟知动态规划有以下的优点：
优点1.减少了计算量，随着段数的增加，计算量大大减少。
优点2.计算中得到了很多有用的中间过程，不仅得到了出发点到终点的最短路径，而且得到了中间各点到终点的最短路径。
二、回顾动态规划的基本思想：
三、通过以下例子，我们将清楚的看到动态规划的优点：（以最短路径为例）
1、段数较少
以下的图为例
说明动态规划的优点，这里我们以整个过程中做的加法次数为指标，次数越少，我们认为计算量越好，效率越高。
穷举法的加法次数：1*2*3*1 = 6
动态规划（逆向D->A）：2*3+1*2 = 8
（说明：动态规划第一步从B->D，不从C->D，C->D不存在选择最短路）
这个似乎不能说明动态规划比穷举法的计算量小，其实是阶段数较少，当阶段数增加后，动态规划的优势明显体现。
2、段数较多
（假设每一层的某个状态都可以到达下一层的每个状态）
穷举法的加法次数：1*2*3*4*4*3*2*1 = 576
动态规划（逆向D->A）：3*2+4*3+4*4+3*4+2*3+1*2 = 54
这下明显可以看出动态的优势，大大减少了计算量；至于说得到有用的中间量，这个不用多解释。
3、量化直接说明动态规划减少计算量的优势
以二中的特殊情况为例，两边对称，段数为偶数的情况，所以一共有2n个阶段（加上始末）。
穷举法的加法次数：（1*2*3*…*n）^2 = （1*2*3*…*n）*（1*2*3*…*n）
动态规划的加法次数：(n*n+(n-1)n+(n-2)(n-1)+...+1*2)*2-1*2< (n*n+(n-1)n+(n-2)(n-1)+...+1*2)*2 < (n*n+(n-1)n+(n-2)n+...+1*n)*2 = (n+(n-1)+(n-2)+...+1)*n*2
当n>3时，（1*2*3*…*n）> (n+(n-1)+(n-2)+...+1) 这个成立，随着n变大差距越越大，毕竟是相乘嘛!
（1*2*3*…*n）> n*2
所以很明显，当段数增加时，动态规划的计算量是成倍成倍的减少。
四、注意动态规划中的无后效性(马尔可夫性)
如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；
过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；
这篇关于讨论动态规划的优点 - 相比于穷举法 - （以最短路径为例）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
