动态规划

动态规划（Dynamic Programming，简称DP）主要解决具有重叠子问题和最优子结构的问题。重叠子问题指递归求解时，相同的子问题会被反复计算，比如斐波那契数列中F(3)被多次计算。DP通过保存子问题答案来避免重复计算，从而提升效率。

假设你爬楼梯，每次可以走1步或2步，问爬到第n阶有多少种方法。定义状态dp[i]表示爬到第i阶的方法数。那么转移方程是dp[i] = dp[i-1] + dp[i-2]，因为到达第i阶只能从i-1跨1步或从i-2跨2步。这就像生活中的决策：当前结果由前两个结果累加得到。

记忆化递归（Memoization）是自顶向下的递归，每次计算前先查表，如果已经算过就直接返回，避免重复。而自底向上填表（Tabulation）是从最小的子问题开始，迭代计算并填表，直到得到最终答案。两者本质相同，但自底向上通常更高效，因为它避免了递归开销。

• 状态：定义dp数组的含义，例如dp[i]表示问题的解。
• 转移方程：状态之间的关系，如dp[i] = dp[i-1] + dp[i-2]。
• 边界条件：最小子问题的解，如dp[0]=1, dp[1]=1。没有边界，转移就无法开始。

常见DP题：0-1背包、最长递增子序列、编辑距离等。这些问题的共同点是：可以分解为重叠子问题，并且当前决策依赖于子问题的解。