动态规划

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

动态规划与递归

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

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

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