03-动态规划基础

4.2　动态规划基础

动态规划是1957年理查德•贝尔曼在《Dynamic Programming》一书中提出来的，可能有的读者不知道这个人，但他的一个算法你可能听说过，他和莱斯特•福特一起提出了求解最短路径的Bellman-Ford 算法，该算法解决了Dijkstra算法不能处理的负权值边的问题。

《Dynamic Programming》中的“Programming”不是编程的意思，而是指一种表格处理法。我们把每一步得到的子问题结果存储在表格里，每次遇到该子问题时不需要再求解一遍，只需要查询表格即可。