目录

原题链接：        

动态规划的基本思想：

爬楼梯题目讲解：

解法1（递归）：

解法2（记忆化递归）：

解法3（Fibonacci数列的动态规划算法）：

总结：

原题链接：70. 爬楼梯 - 力扣（LeetCode）

        动态规划（Dynamic Programming，简称DP）是一种算法设计技术，它通过将复杂问题分解为更小的子问题来解决优化问题。动态规划通常用于解决具有重叠子问题和最优子结构特性的问题。         动态规划的基本思路可以概括为以下几个步骤：                 1. 定义状态：首先，需要定义问题中的状态。状态是指在特定步骤或阶段的问题的某种描述。通常，状态可以用一个或多个变量来表示，并且状态之间存在依赖关系。                 2. 状态转移方程：其次，确定状态转移方程，也称为递推关系。这个方程描述了状态如何从之前的某个状态或多个状态转移而来。在形式上，这个方程通常表示为 `dp[i] = f(dp[i-1], dp[i-2], ...)`，其中 `dp[i]` 是到达第 `i` 个状态的方法数或成本，而 `f` 是一个关于前状态的函数。                 3. 边界条件：确定初始状态或边界条件。这些是问题的基础情况，通常可以直接计算得到，或者由问题的性质直接给出。                 4. 计算顺序：确定状态的计算顺序。通常，状态的计算顺序应该能够充分利用之前计算的结果，避免重复计算。                 5. 构建DP表：根据状态转移方程和边界条件，构建一个DP表（或数组），并按顺序填充表中的每个状态。                 6. 输出结果：最后，根据DP表中的最终状态输出结果。

        动态规划的关键优点是它能够显著减少计算复杂度，将指数级问题转化为多项式级问题。这主要是因为动态规划避免了重复计算相同的状态，而是利用已计算的状态结果。

        动态规划适用于具有最优子结构特性的问题，即一个问题的最优解包含了其子问题的最优解。此外，动态规划也适用于具有重叠子问题的问题，即在求解问题的过程中，相同的子问题会被多次计算。通过存储这些子问题的解，动态规划可以有效地减少计算量。

        Fibonacci（斐波那契）数列问题，它是一个简单而典型的分治问题，Fibonacci数列的递归方程表示为：

        F(n) = F(n-1) + F(n-2)；

        其中，F(n) 表示数列的第n项，F(n-1) 表示数列的第n-1项，F(n-2) 表示数列的第n-2项。

        注意，这个递归方程是从第三项开始的，因为前两项有明确的定义：

        F(0) = 0 ；

        F(1) = 1。

        该程序实现简单，但非常低效。以求解该题目不难发现，在递归调用过程中，每次产生的子问题并不是新问题，有些子问题被反复计算多次，比如climbStairs（3）调用了两次，climbStairs（2）调用了三次，这种现象被称为 重叠子问题。

        当输入参数n较大时，其重复计算的子问题数目将爆照式增长，最终需要计算的子问题个数（或者递归调用次数）将增长为指数级。

那么该如何减少实际求解的子问题的数目呢？

        如果用一个数组保存已解决的子问题的答案，而在需要时再从该数组中查找已经求解的子问题的答案，这样就可以避免大量的重复计算，从而得到多项式复杂性算法。这就是动态规划的基本思路。

        记忆化（缓存）：由于递归会多次计算相同的子问题，这会导致大量的重复计算，特别是在 n 较大时。为了避免重复计算，我们可以使用一个数组 arr 来存储已经计算过的结果。如果 arr[n] 已经被计算过，就直接返回它的值，否则就计算它并存储起来。