动态规划

动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段决策问题”，利用各个阶段阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决策。

动态规划与递归

• 动态规划本质上不是递归，甚至可以理解是和递归相反的一种算法设计思想。

• 递归是自顶向下的，从顶部开始分解问题，然后通过解决分解出的小问题，从而解决出整个问题

• 动态规划是自底向上的，从底部开始解决问题，按照顺序一步一步扩大问题的规模从而去解决整个问题