 空间解法)
CS-Notes 剑指 Offer 动态规划:跳台阶问题的递推建模与 O(1) 空间解法【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库中「剑指 Offer」动态规划专题的跳台阶题解,围绕青蛙每次跳 1 级或 2 级台阶,求跳上 n 级台阶的跳法总数这一问题展开:从递推公式的推导、朴素递归的缺陷,到滚动变量实现的空间优化,完整给出可复现的 Java 解法,并串联斐波那契数列、矩形覆盖、变态跳台阶三道同型题目,帮助读者掌握递推建模范式与O(1) 空间动态规划两类面试核心能力。一、问题定义一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。这道题出自「剑指 Offer」经典题库,在 CS-Notes 的剑指 Offer 题解目录中被归入「动态规划」专题,与 10.1 斐波那契数列、10.2 矩形覆盖、10.4 变态跳台阶 组成一组同型题。二、递推建模:从小规模实例中找规律先观察两个最小规模的边界情况,它们是后续递推公式的基石:n 1 时,只有 1 种跳法:即跳 1 级。n 2 时,有 2 种跳法:先跳 1 级再跳 1 级,或者一次跳 2 级。关键在于最后一跳的状态划分:要跳上第 n 级台阶,青蛙倒数第一步只有两种可能——从第 n-1 级跳 1 级上来,那么前 n-1 级的跳法总数就是f(n-1);从第 n-2 级跳 2 级上来,那么前 n-2 级的跳法总数就是f(n-2)。两种情况互斥且穷尽,因此得到递推公式(原文档以图片形式给出):用数学语言表述即:f(1) 1 f(2) 2 f(n) f(n-1) f(n-2), n 2从源码结构看,这个递推关系与 CS-Notes 中 10.1 斐波那契数列 的f(n) f(n-1) f(n-2)完全同型,只是初始条件不同——跳台阶本质上是偏移了一位、且从 1, 2 起步的斐波那契数列;10.2 矩形覆盖(用 n 个 2×1 小矩形覆盖 2×n 大矩形)的递推公式也与之一字不差。三者共享同一套求解框架:确定初始条件 → 写出状态转移方程 → 自底向上迭代。三、解法演进:从朴素递归到滚动变量3.1 朴素递归:指数级开销按递推式直接写递归,是最直觉的写法:public int JumpFloor(int n) { if (n 2) return n; return JumpFloor(n - 1) JumpFloor(n - 2); }但正如 10.1 斐波那契数列 中所分析的那样,递归会把子问题反复计算:计算f(5)需要计算f(4)和f(3),而f(4)内部又要计算f(3)和f(2),f(3)被重复求解。调用树近似呈二叉展开,时间复杂度为指数级 O(2^n),n 稍大(如超过 40)就会超时,面试中不可接受。3.2 自底向上动态规划:O(n) 时间用缓存子问题解的思路,自底向上填表:public int JumpFloor(int n) { if (n 2) return n; int[] dp new int[n 1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) dp[i] dp[i - 1] dp[i - 2]; return dp[n]; }时间复杂度降为 O(n)。但进一步观察可以发现:dp[i]只依赖dp[i-1]与dp[i-2]两个状态,历史状态一旦用完就不再需要。这正是原仓库 10.3 跳台阶 给出的优化方向。3.3 滚动变量:O(1) 空间(原文档标准解法)原文档给出的最终实现如下,仅用两个变量pre2、pre1滚动保存前两项:public int JumpFloor(int n) { if (n 2) return n; int pre2 1, pre1 2; int result 0; for (int i 2; i n; i) { result pre2 pre1; pre2 pre1; pre1 result; } return result; }逐行拆解这段代码的参数含义与执行过程:变量初始值含义pre21对应f(1) 1pre12对应f(2) 2result0存放当前正在计算的f(i1)循环i 2; i n; i—从第 3 项开始,共滚动 n-2 次,结束时result恰为f(n)以 n 5 为例跟踪循环:轮次 iresult(即 f(i1))pre2pre123 f(3)2335 f(4)3548 f(5)58最终返回result 8,即跳 5 级台阶共 8 种跳法,时间复杂度 O(n)、空间复杂度 O(1)。这与 10.1 斐波那契数列 中考虑到第 i 项只与第 i-1 和第 i-2 项有关,只需存储前两项,将空间复杂度由 O(N) 降为 O(1)的优化思想如出一辙。3.4 边界与数值限制说明结合原实现if (n 2) return n;的写法,从源码结构看,该方法对 n ≤ 0 的输入会直接返回 n 本身(即 0 或负数),题目隐含 n 为正整数这一前提,实际调用前应对输入合法性做校验。另外,由于返回值是int,而跳台阶的解就是斐波那契数列,Fib(47) 已超过 32 位整数上限,因此 n 较大(约 46 以上)时该解法会发生整数溢出;若题目允许 n 更大,可改用long或取模运算,这一点与 10.1 斐波那契数列 中n ≤ 39的取值约束是同一类考虑。四、同型题对照:一道题串起整个 DP 专题在 CS-Notes 的动态规划分组中,跳台阶是承上启下的一题,建议配合以下文档横向对比学习:题目状态转移方程结果特征文档10.1 斐波那契数列f(n) f(n-1) f(n-2)斐波那契数列本体,可用 O(1) 预计算notes/10.1 斐波那契数列.md10.2 矩形覆盖f(n) f(n-1) f(n-2)与跳台阶同方程同解法notes/10.2 矩形覆盖.md10.3 跳台阶f(n) f(n-1) f(n-2)本文主题,O(n) 时间 O(1) 空间notes/10.3 跳台阶.md10.4 变态跳台阶f(n) f(n-1) ... f(0)化为等比数列f(n) 2^(n-1)notes/10.4 变态跳台阶.md其中 10.4 变态跳台阶 是最有价值的变式:若青蛙可以跳 1 级到 n 级,则状态转移变成求和式f(n) f(n-1) f(n-2) ... f(0)。由相邻两式相减可得f(n) 2 * f(n-1),即 f(n) 是等比数列,最终解为:public int JumpFloorII(int target) { return (int) Math.pow(2, target - 1); }对比之下可以清晰看出:「跳台阶」的 O(n) 迭代与「变态跳台阶」的 O(1) 公式解,差异完全来自状态转移方程的形态。面试中被追问如果青蛙可以跳任意级怎么解,正是靠这种对比能力得分。五、小结与面试表达要点回顾 10.3 跳台阶 的完整解题脉络,面试作答可按以下逻辑链组织:建模:按最后一跳划分状态,得到f(n) f(n-1) f(n-2),初始条件f(1) 1、f(2) 2;排除:朴素递归存在大量重叠子问题,时间复杂度指数级,不可取;实现:自底向上迭代,且利用状态只依赖前两项这一性质,用pre2/pre1滚动变量把空间压到 O(1);延伸:主动提及矩形覆盖(同方程)、斐波那契(同型递推)、变态跳台阶(等比数列化简2^(n-1))三道关联题,展示对整个 DP 专题的把握。这套划分最后一步 → 写出转移方程 → 迭代滚动优化的三步法,可直接迁移到绝大多数一维递推类面试题,是 CS-Notes 动态规划专题最具复用价值的方法论。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
CS-Notes 剑指 Offer 动态规划:跳台阶问题的递推建模与 O(1) 空间解法【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库中「剑指 Offer」动态规划专题的跳台阶题解,围绕青蛙每次跳 1 级或 2 级台阶,求跳上 n 级台阶的跳法总数这一问题展开:从递推公式的推导、朴素递归的缺陷,到滚动变量实现的空间优化,完整给出可复现的 Java 解法,并串联斐波那契数列、矩形覆盖、变态跳台阶三道同型题目,帮助读者掌握递推建模范式与O(1) 空间动态规划两类面试核心能力。一、问题定义一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。这道题出自「剑指 Offer」经典题库,在 CS-Notes 的剑指 Offer 题解目录中被归入「动态规划」专题,与 10.1 斐波那契数列、10.2 矩形覆盖、10.4 变态跳台阶 组成一组同型题。二、递推建模:从小规模实例中找规律先观察两个最小规模的边界情况,它们是后续递推公式的基石:n 1 时,只有 1 种跳法:即跳 1 级。n 2 时,有 2 种跳法:先跳 1 级再跳 1 级,或者一次跳 2 级。关键在于最后一跳的状态划分:要跳上第 n 级台阶,青蛙倒数第一步只有两种可能——从第 n-1 级跳 1 级上来,那么前 n-1 级的跳法总数就是f(n-1);从第 n-2 级跳 2 级上来,那么前 n-2 级的跳法总数就是f(n-2)。两种情况互斥且穷尽,因此得到递推公式(原文档以图片形式给出):用数学语言表述即:f(1) 1 f(2) 2 f(n) f(n-1) f(n-2), n 2从源码结构看,这个递推关系与 CS-Notes 中 10.1 斐波那契数列 的f(n) f(n-1) f(n-2)完全同型,只是初始条件不同——跳台阶本质上是偏移了一位、且从 1, 2 起步的斐波那契数列;10.2 矩形覆盖(用 n 个 2×1 小矩形覆盖 2×n 大矩形)的递推公式也与之一字不差。三者共享同一套求解框架:确定初始条件 → 写出状态转移方程 → 自底向上迭代。三、解法演进:从朴素递归到滚动变量3.1 朴素递归:指数级开销按递推式直接写递归,是最直觉的写法:public int JumpFloor(int n) { if (n 2) return n; return JumpFloor(n - 1) JumpFloor(n - 2); }但正如 10.1 斐波那契数列 中所分析的那样,递归会把子问题反复计算:计算f(5)需要计算f(4)和f(3),而f(4)内部又要计算f(3)和f(2),f(3)被重复求解。调用树近似呈二叉展开,时间复杂度为指数级 O(2^n),n 稍大(如超过 40)就会超时,面试中不可接受。3.2 自底向上动态规划:O(n) 时间用缓存子问题解的思路,自底向上填表:public int JumpFloor(int n) { if (n 2) return n; int[] dp new int[n 1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) dp[i] dp[i - 1] dp[i - 2]; return dp[n]; }时间复杂度降为 O(n)。但进一步观察可以发现:dp[i]只依赖dp[i-1]与dp[i-2]两个状态,历史状态一旦用完就不再需要。这正是原仓库 10.3 跳台阶 给出的优化方向。3.3 滚动变量:O(1) 空间(原文档标准解法)原文档给出的最终实现如下,仅用两个变量pre2、pre1滚动保存前两项:public int JumpFloor(int n) { if (n 2) return n; int pre2 1, pre1 2; int result 0; for (int i 2; i n; i) { result pre2 pre1; pre2 pre1; pre1 result; } return result; }逐行拆解这段代码的参数含义与执行过程:变量初始值含义pre21对应f(1) 1pre12对应f(2) 2result0存放当前正在计算的f(i1)循环i 2; i n; i—从第 3 项开始,共滚动 n-2 次,结束时result恰为f(n)以 n 5 为例跟踪循环:轮次 iresult(即 f(i1))pre2pre123 f(3)2335 f(4)3548 f(5)58最终返回result 8,即跳 5 级台阶共 8 种跳法,时间复杂度 O(n)、空间复杂度 O(1)。这与 10.1 斐波那契数列 中考虑到第 i 项只与第 i-1 和第 i-2 项有关,只需存储前两项,将空间复杂度由 O(N) 降为 O(1)的优化思想如出一辙。3.4 边界与数值限制说明结合原实现if (n 2) return n;的写法,从源码结构看,该方法对 n ≤ 0 的输入会直接返回 n 本身(即 0 或负数),题目隐含 n 为正整数这一前提,实际调用前应对输入合法性做校验。另外,由于返回值是int,而跳台阶的解就是斐波那契数列,Fib(47) 已超过 32 位整数上限,因此 n 较大(约 46 以上)时该解法会发生整数溢出;若题目允许 n 更大,可改用long或取模运算,这一点与 10.1 斐波那契数列 中n ≤ 39的取值约束是同一类考虑。四、同型题对照:一道题串起整个 DP 专题在 CS-Notes 的动态规划分组中,跳台阶是承上启下的一题,建议配合以下文档横向对比学习:题目状态转移方程结果特征文档10.1 斐波那契数列f(n) f(n-1) f(n-2)斐波那契数列本体,可用 O(1) 预计算notes/10.1 斐波那契数列.md10.2 矩形覆盖f(n) f(n-1) f(n-2)与跳台阶同方程同解法notes/10.2 矩形覆盖.md10.3 跳台阶f(n) f(n-1) f(n-2)本文主题,O(n) 时间 O(1) 空间notes/10.3 跳台阶.md10.4 变态跳台阶f(n) f(n-1) ... f(0)化为等比数列f(n) 2^(n-1)notes/10.4 变态跳台阶.md其中 10.4 变态跳台阶 是最有价值的变式:若青蛙可以跳 1 级到 n 级,则状态转移变成求和式f(n) f(n-1) f(n-2) ... f(0)。由相邻两式相减可得f(n) 2 * f(n-1),即 f(n) 是等比数列,最终解为:public int JumpFloorII(int target) { return (int) Math.pow(2, target - 1); }对比之下可以清晰看出:「跳台阶」的 O(n) 迭代与「变态跳台阶」的 O(1) 公式解,差异完全来自状态转移方程的形态。面试中被追问如果青蛙可以跳任意级怎么解,正是靠这种对比能力得分。五、小结与面试表达要点回顾 10.3 跳台阶 的完整解题脉络,面试作答可按以下逻辑链组织:建模:按最后一跳划分状态,得到f(n) f(n-1) f(n-2),初始条件f(1) 1、f(2) 2;排除:朴素递归存在大量重叠子问题,时间复杂度指数级,不可取;实现:自底向上迭代,且利用状态只依赖前两项这一性质,用pre2/pre1滚动变量把空间压到 O(1);延伸:主动提及矩形覆盖(同方程)、斐波那契(同型递推)、变态跳台阶(等比数列化简2^(n-1))三道关联题,展示对整个 DP 专题的把握。这套划分最后一步 → 写出转移方程 → 迭代滚动优化的三步法,可直接迁移到绝大多数一维递推类面试题,是 CS-Notes 动态规划专题最具复用价值的方法论。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
