一文读懂动态规划

动态规划（DP, Dynamic Programming）是很多互联网公司笔试/面试喜欢考的题目，听起来也非常高大上。对于非计算机专业，或者没怎么刷过编程题的人来说，可能会对这个算法望而生畏。这里分享一下，让大家一看就明白，理解到底什么是动态规划。

动态规划最主要的思想是把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

看例子：

有N个公交站，不妨编号为0,1,2, ……N-1，从起点站0做公交车，可以直接坐到终点站N-1；也可以从站0先坐到站1，然后从站1坐到站N-1；或者多中转几站也可以到达终点站。现在给定任意两站的价格，问：如何中转使得总价最低？

具体地，比如现在有0, 1, 2, 3一共4个站点，从站点0到站点1费用是1元，记做0->1：1，给定所有站点之间的费用为：

0->1：1
0->2：2
0->3：4
1->2：2
1->3：3
2->3：1

如果想从0到3，可以0->3费用是4元；也可以0->2，再2->3，费用是2+1=3元；也可以0->1，再1->3，费用是1+3=4元；或者是0->1，再1->2，再2->3，费用是1+2+1=4元。可以看出，0->2，2->3这种方案价格最低。

这是一个简单的例子，在考虑算法解决的时候，显然不能按照上面穷举的方式，而是需要思考效率更高的解法。

需要解决的问题是找到从首站0到末站N-1价格最低的方案，这个路径有点多，可以这样考虑：如果可以得到0->N-2，0->N-3……的最优方案，那0->N-1的最优方案能否由这些已知的最优方案再经过一些计算得到呢？确实是可以的，因为：0->N-1的最优方案肯定是下面这些方案之一：

0->N-2（最优）+ N-2->N-1

0->N-3（最优）+ N-3->N-1

…

如果可以得到0->N-2最优方案，0->N-3的最优方案，那0->N-1的最优方案就是比较上面这些方案，找总价最低的就可以了。具体算法运行的时候可以从0开始往下算，得到0->1的最优解，然后算0->2的最优解，以此类推，最后就可以轻松求得0->N-1的最优解，当然，也顺路得到了站到0到所有站点的最优解。

因此，动态规划的难点在于路径太多，思路在于要逐步求解，后面的步骤要利用前面步骤算出的结果，这样避免重复计算路径，效率最高~

最后，动态规划在实际业务用会用到吗？我看是不太会，实际公交车基本上从哪一站算价格都是差不多的，中转肯定不会省钱。。很多编程和算法题更像是训练思维，一种解决问题的思路，就像微积分，业务中也基本不会用到，但在大学还是要学。就当做是做游戏，找个乐也是不错的。

公众号持续更新，欢迎订阅。

AI人工智能与大数据