type
Post
status
Published
date
Mar 1, 2026
slug
summary
tags
算法笔记
category
笔记
icon
password
动态规划的关键在于找到解决问题的方法，所以如果你能找到问题解决的策略，你就可以解决任何动态规划问题。
- 遵循最优性原理
- 一个问题可以由一系列的决策来解决，从而获得最优解。
- 在解决问题的每个阶段都需要做出决策，这一点可以在解决问题的过程中理解它是如何工作的。
- 斐波拉契函数
- 斐波拉契函数定义如下：
- 当
n <= 1时，直接返回，这是常数时间，记为 O(1)。 - 当
n > 1时，需要计算fib(n-1)和fib(n-2)，再加上一次加法操作。因此，递推关系为：T(n) = T(n-1) + T(n-2) + O(1) ~ 2T(n-1)+ O(1) - 由主定理知：时间复杂度属于 级别。
- 在 fib(5)的递归树中，fib(3)、fib(2)、fib(1)等都被计算了多次。随着 n增大，这种重复是指数级增长的。
b.伪代码如下：
c.设
T(n)为计算 fib(n)所需的基本操作次数。根据代码：d.核心结论:斐波那契递归算法效率低下的根源，与
T(n) = 2T(n-1) + 1所揭示的问题本质相同：存在大量完全相同的重复子问题计算。如何改进斐波拉契函数？—— 从指数到线性的飞跃
理解了递归树和重复计算的问题，改进方案就非常直观了：
- 记忆化（自顶向下的动态规划）：用一个缓存（数组或字典）存储已经计算过的
fib(k)的结果。当需要再次计算时，直接从缓存中读取，避免重复的递归调用。这样每个fib(k)只计算一次，时间复杂度降至 O(n)。
- 动态规划（自底向上迭代）：直接从
fib(0)和fib(1)开始，循环计算到fib(n)。这是最高效的方法，时间复杂度 O(n)，空间复杂度可以优化到 O(1)（只存储前两个值，大多数动态规划问题可以配合制表法分析）。——代码如何写？
代码
- Author:RHZ
- URL:http://www.rhzhz.cn/article/3169daca-95bb-8099-8fe6-ca91e95e72d9
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
