网站导航
> 技术文档 > 【递推-动态规划-复杂度】（重视概念）写给初学者-从一个影视作品入手——高中生的随笔

【递推-动态规划-复杂度】（重视概念）写给初学者-从一个影视作品入手——高中生的随笔

网友: 技术文档 2025-09-02 19:12:51

前言

准高一 ~ 

刚才刷B站电影解说，刷到了这个《少年班》中的一个片段

其中王大法用龟壳和周易解决了一道动态规划的题目，很有趣

我将先给出最终程序，再依次将逻辑思想娓娓道来

本文编写耗费近4小时，包括自己查找，学习理解这些概念，以及整理分析和文章的书写

如果有不准确不严谨的地方欢迎纠正，这个标题目录层级关系没太搞明白多多包容

部分表格请求了DeepSeek的帮助，其他为我自己的劳动成果！请求点赞收藏【爱心】

题目以及答案

题目大致如下：

20阶楼梯

每次上1层或2层

一共多少种上法

答案：10964种

那为何呢？

 程序实现

C++

#include #include using namespace std;int climbStairs(int n) { if (n <= 2) return n; // 创建一个\"笔记本\"（数组）来记录已计算的结果 vector dp(n + 1); // 记录基础情况 dp[1] = 1; // 只有1阶楼梯时的走法 dp[2] = 2; // 有2阶楼梯时的走法 // 从3开始逐步计算到n，每次都查阅\"笔记本\"中的已有结果 for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; // 使用递推关系 } return dp[n];}int main() { int n = 20; cout << \"爬 \" << n << \" 阶楼梯的方法数为: \" << climbStairs(n) << endl; return 0;}

Python

def climb_stairs(n): if n <= 2: return n # 创建一个\"笔记本\"（列表）来记录已计算的结果 dp = [0] * (n + 1) # 记录基础情况 dp[1] = 1 # 只有1阶楼梯时的走法 dp[2] = 2 # 有2阶楼梯时的走法 # 从3开始逐步计算到n，每次都查阅\"笔记本\"中的已有结果 for i in range(3, n + 1): dp[i] = dp[i - 1] + dp[i - 2] # 使用递推关系 return dp[n]# 测试n = 20print(f\"爬 {n} 阶楼梯的方法数为: {climb_stairs(n)}\")

概念讲解

先讲讲这道题需要了解的概念

递推

简单但是很重要

（选自百度百科）

不需要从头开始解决一个大难题，而是想着：“如果我知道前面几个小问题的答案，我能不能很容易地推出这个大问题的答案？” 

就好比你知道昨天和今天的天气，可以大致推测明天一样。它的核心是找到问题之间的这种“推导关系”。

基础情况

说实话我不确定这算不算一个概念，但还是了解一下更好

这是你“推理链条的起点”，是那些最简单、不用再推就知道答案的情况。

动态规划 ( DP)

核心思想：别干重复的工作！

动态规划就是“聪明的做笔记方法”

在解决问题的过程中，你会遇到很多重复的小问题。动态规划就是让你把每个小问题的答案都记在本子上，下次再遇到时，直接查笔记就行了，不用再吭哧吭哧重新算一遍。

为什么很重要？

一种“用空间换时间”的算法思想，通过存储子问题的解来避免重复计算，极大提升效率。

动态规划的三步操作法：

  1. 拆解问题 (找子问题)

    • 问自己： 解决这个大问题的前提，是不是先要解决几个一模一样的小问题？

    • 比如爬楼梯： 想知道“到20楼有多少种走法？”（大问题），你先得知道“到19楼有多少种？”和“到18楼有多少种？”（小问题）。这些小问题和大问题的模式完全一样。

  2. 记住答案 (做笔记)

    • 准备一个“笔记本”（在程序里叫数组或字典）。每解决一个小问题，就立刻把答案记下来。

    • 比如爬楼梯： 你算出来“到3楼有3种走法”，马上在笔记本上写 F[3] = 3。

  3. 组合答案 (查笔记)

    • 当你要解决一个大问题时，先去笔记本里找，它依赖的那些小问题是不是已经解决了？如果解决了，直接查笔记！组合一下就能得到大问题的答案。

    • 比如爬楼梯： 要算 F[5]，你不是重新去算 F[4] 和 F[3]，而是直接翻开笔记本，找到之前已经算好的 F[4]=5 和 F[3]=3，把它们加起来 5+3=8，得到 F[5]=8。再把8记到笔记本上

复杂度

总结对比：

方面 时间复杂度 空间复杂度 关心什么 时间增长的趋势 空间（内存）增长的趋势 目标 让算法跑得更快 让算法吃得更少（内存） 好坏顺序 O(1) < O(log n) < O(n) < O(n²) < O(2^n) O(1) < O(n) < O(n²)

时间复杂度

我之前一直以为这个单纯表示你程序运行的时间长短，不过我好在写这个文章之前搜索了一下，要不然真说错了

时间复杂度关心的是：当数据量变大时，程序运行时间增长的趋势

数据规模：你要处理数据的量

运行时间：处理所用的时间

时间复杂度就是用来衡量“运行时间”随着“数据规模”增加而增长的趋势。

常见类型和计算方法（看趋势！）

我们不用精确计算，只看最高次项，并且忽略常数。因为当n非常大时，只有最高次项才起决定性作用。（以下是我请求DeepSeek生成的一个表格，附带一些通俗的比喻）

（本人没这个文采和实力......哭泣......）

类型 俗称 切菜比喻 计算例子 趋势 O(1) 常数时间 不管有多少菜，你有一把菜刀机枪，一下全切完。工夫恒定。 数组根据下标取元素 arr[1000] 一条水平线，完美！ O(log n) 对数时间 每次切一半扔一半。菜越多，优势越明显，工夫增长得很慢。 二分查找 几乎像平的，非常高效！ O(n) 线性时间 你有一把普通菜刀，切一根黄瓜要1秒。10根黄瓜就要10秒。工夫和菜量成正比。 遍历数组找数 for(int i=0; i<n; i++) 一条斜线，还不错。 O(n log n) 更好的排序算法。可以理解为：做了log n轮，每轮要处理n个菜。 快速排序，归并排序 比斜线抖一点，但很好。 O(n²) 平方时间 你是个强迫症，每根黄瓜不仅要切，还要和其他每一根都比一下长短。10根黄瓜要比100次。 双层嵌套循环 for(i){ for(j){} } 陡峭的曲线，菜一多就累死。 O(2^n) 指数时间 灾难！ 切菜方法会爆炸性增长。每多一根黄瓜，你要干的活儿直接翻倍！ 暴力穷举所有组合，比如算斐波那契数列的递归 一条近乎垂直的线，非常可怕！

那么我们来总结一下常见的情况吧

怎么算？

为什么我用词是“很大可能”？

因为这终归决定于你代码的底层逻辑，而不是长相

  • 1层循环 -> 很大可能是 O(n)

  • 2层嵌套循环 -> 很大可能是 O(n²)

  • 循环里每次数据折半 -> 很大可能是 O(log n)

  • 没有循环，直接计算 -> O(1)

空间复杂度

这个概念后面的其实我没怎么看懂，那我就大概的讲讲基本概念

空间复杂度就是衡量“所需内存”随着“处理数据”增加而增长的趋势。注意： 空间复杂度不算数据本身占的地方，算的是你为了加工它们而额外需要的空间。

常见类型和计算方法

以下我同样请DeepSeek帮我生成一个讲解，看着很通俗

类型 比喻 计算例子 O(1) 不管你原材料有多少，你只需要一把剪刀和一瓶胶水。桌面大小是固定的。 爬楼梯问题中，只用2个变量 a 和 b 来回倒腾。 O(n) 你需要把每个原材料都先对应地放到一个格子里。原材料增加一倍，你需要的格子（数组）也大一倍。 开辟了一个长度为n的数组 dp[n] 来存储中间结果。 O(n²) 你不仅需要放原材料的格子，还需要一个巨大的棋盘来记录每两个原材料之间的关系。 开辟了一个二维数组 dp[n][n]。
怎么算？

看你的代码里额外开了多大的数组、容器或者递归调用了多深：

（以下我整理了查到的结果，如有不准确期待纠正！！）

  • 只用了几个固定变量 -> O(1)

  • 开了一个和输入数据n一样长的数组 -> O(n)

  • 开了一个n x n的二维数组 -> O(n²)

  • 递归调用，调用栈的深度是n -> O(n) (因为每一层调用都要在内存中保存信息)

问题分析

给定 n 阶楼梯，每次只能上 1 阶或 2 阶，求上到楼顶的所有可能方式的数量。

这是一个经典的动态规划问题，其最优子结构体现在：到达第 n 阶的方法数等于到达第 n-1 阶和 n-2 阶方法数之和。

递推关系

定义 dp[i] 为到达第 i 阶楼梯的方法数，则递推关系为：

dp[i] = dp[i-1] + dp[i-2]

基础情况：

dp[1] = 1 # 只有一种方式：上一阶dp[2] = 2 # 两种方式：两次一阶或一次两阶

以下我将要将递推很重要的分析，一定要搞清楚！

想象一下，你终于站到了第20阶楼梯上（恭喜！）。现在，请你回头看最后一步，你只可能是从下面两种地方上来的：

  1. 从第 19 阶楼梯（爬了1阶上来）

  2. 从第 18 阶楼梯（爬了2阶上来）

关键问题来了：

  • 爬到第19阶有多少种走法？（我们记作 F(19) 种）

  • 爬到第18阶有多少种走法？（我们记作 F(18) 种）

那么，你所有爬到第20阶的走法，无非就是：

  • (所有爬到第19阶的走法) + 最后一步走1阶

  • (所有爬到第18阶的走法) + 最后一步走2阶

所以，爬到第20阶的总方法数 F(20)，就等于 F(19) + F(18)。

这就是我们的“递推关系”：
F(n) = F(n-1) + F(n递推关系理解好，我们需要找一个起点，也就是递推的开始

递推需要一个起点，就像盖房子需要地基。我们需要手动定义最简单的情况。

  • F(1)：只有1阶楼梯，有几种走法？

    • 只有1种：走1阶。

    • 所以 F(1) = 1

  • F(2)：有2阶楼梯，有几种走法？

    • 有2种：一次走2阶 或者 走两次1阶。

    • 所以 F(2) = 2

这是地基，我们可以从这里推导出来3,4,5......等情况

F(3) = F(2) + F(1) = 2 + 1 = 3
F(4) = F(3) + F(2) = 3 + 2 = 5
F(5) = F(4) + F(3) = 5 + 3 = 8
...
一直算到 F(20)。

但是？是不是有点太费力气了，效率低下，原因在于

比如你想算 F(20)：

  • 电脑需要算 F(19) 和 F(18)

  • 算 F(19) 又要去算 F(18) 和 F(17)

  • 算 F(18) 又要去算 F(17) 和 F(16)

动态规划的使用

于是就要使用到动态规划，记住算过的答案

我们可以这样做：

  1. 开一个本子（一个数组），先记下 F(1)=1, F(2)=2。

  2. 然后按顺序，从3开始一直算到20。

  3. 算 F(3) 时，直接翻看本子上 F(2) 和 F(1) 的值，加起来得到 3，并记到本子上。

  4. 算 F(4) 时，直接翻看本子上 F(3) 和 F(2) 的值，加起来得到 5，并记下。

  5. ... 以此类推。

这样，每个值我们只计算一次，大大提高了效率。

聊聊效率——时间复杂度和空间复杂度

  • 时间复杂度：衡量算法跑得有多快。

    • 笨方法（递归）： 像树一样不断分叉，时间呈指数级（Exponential） 增长。O(2^n)。算20阶可能还行，算50阶电脑就累瘫了。

    • 聪明方法（动态规划）： 我们只从1到20顺序计算了一遍，时间是线性（Linear） 的。O(n)。就算算1000阶也很快。

  • 空间复杂度 (Space Complexity)：衡量算法需要占用多少内存。

    • 算新的值只需要前两个值。所以我们只需要两个变量来记录 F(n-1) 和 F(n-2) 就行了，空间是常数（Constant） 的。O(1)。非常节省内存。

结尾

感谢大家到现在的学习，如果有任何问题欢迎留言评论

求关注点赞收藏~

网络标签：

相关问题