Introduction - Dynamic Programming

先导篇 - 动态规划思想

动态规划，又称为"DP"（Dynamic Programming）

知识回顾

动态规划是一种通过将原问题分解为子问题来求解复杂问题的算法思想。它通常用于求解最优化问题，例如最长公共子序列、背包问题等。动态规划的核心思想是将原问题分解为若干个子问题，通过求解子问题的最优解推导出原问题的最优解。可以通过两点来判断一个问题能不能通过动态规划来解，一是该问题是否存在递归结构，二是对应的子问题能否记忆化。动态规划可以通过带备忘录的自上而下的递归和自下而上的迭代来分别实现。由于递归需要用到栈来实现，一些语言对递归的深度是有限制的，所以自下而上的迭代是动态规划的最佳实现方式。

分为：

• 自上而下：递归调用：从 fib(n) 推到 fib(n-1)\fib(n-2) 的过程

• 自下而上：递推公式：for 循环从 fib(0)\fib(1) 推到 fib(n) 的过程

在实际做题时候，可以先用递归来判断这道题是否能用动态规划的思路。如果成功了，可以改写为迭代。在一维动态规划的问题中，迭代法甚至可以不需要额外的空间复杂度。

动态规划两个特征：

• 递归

• 出现重复子问题