真爱难求 發表於 2025-7-8 09:00:00

剑指offer-9-变态跳台阶

<h2 id="题描述">题⽬描述</h2>
<p>⼀只⻘蛙⼀次可以跳上1 级台阶，也可以跳上2级……它也可以跳上n级。求该⻘蛙跳上⼀个n级的台阶总共有多少种跳法。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="数学归纳法">数学归纳法</h3>
<p>⾸先⻘蛙⼀次可以跳 1 , 2 , 3 到 n 级。假设函数是f(n) ，则：</p>
<ul>
<li>⻘蛙跳到第⼀级是f（1）=1 ，只有⼀种跳法。</li>
<li>⻘蛙跳到第⼆级，可以是直接跳到第⼆级，也可以是从第⼀级直接跳。所以f(2)=f(1)+1</li>
<li>⻘蛙跳到第三级，可以从第0 级跳，也可以从第1级跳，也可以从第2 级跳。所以f(3)=f(1)+f(2)+1 ;</li>
<li>依次类推，⻘蛙跳到第n 级，可以是从0 , 1 , 2 , 3 .. (n-1) 级跳，所以f(n)=f(1)+f(2)+f(3)...+f(n-1)+1 ;</li>
</ul>
<p>进一步观察可以发现：</p>
<ul>
<li>f(1) = 1</li>
<li>f(2) = f(1) + f(0) = 2</li>
<li>f(3) = f(2) + f(1) + f(0) = 4</li>
<li>f(4) = f(3) + f(2) + f(1) + f(0) = 8</li>
</ul>
<p>显然，这是一个等比数列，通项公式为f(n) = 2^(n-1)。这个发现将问题简化为简单的幂次计算</p>
<pre><code class="language-java">public class Solution {
    public int JumpFloorII(int target) {
                        if (target &lt;= 0) return 0;
      return (int) Math.pow(2, target - 1);
    }
}
</code></pre>
<ul>
<li>时间复杂度：O(1)，直接计算幂次</li>
<li>空间复杂度：O(1)，仅使用常数空间</li>
</ul>
<p>数学归纳法的优势在于将问题转化为已知的数学公式，但需要较强的数学观察能力才能发现其中的规律</p>
<h3 id="递归">递归</h3>
<p>将大问题分解为小问题来解决。对于n级台阶，青蛙第一次跳跃可以有n种选择：跳1级、跳2级，...，跳n级。如果第一次跳1级，剩下n-1级有f(n-1)种跳法；如果第一次跳2级，剩下n-2级有f(n-2)种跳法；依此类推，直到第一次直接跳n级，有1种跳法。</p>
<p>因此，递归公式为：f(n) = f(n-1) + f(n-2) + ... + f(1) + 1</p>
<p>而f(n-1) = f(n-2) + ... + f(1) + 1</p>
<p>两式相减可得：f(n) = 2*f(n-1)，</p>
<pre><code class="language-java">public class Solution {
    public int JumpFloorII(int target) {
                if (target &lt;= 0) return 0;
      if (target == 1) return 1;
      return 2 * jump(target - 1);
    }
}
</code></pre>
<ul>
<li>时间复杂度：O(n)，需要n次递归调用</li>
<li>空间复杂度：O(n)，递归调用栈深度为n</li>
</ul>
<p>递归解法虽然代码简洁，但当n较大时会出现栈溢出风险，且存在大量重复计算，效率较低</p>
<h3 id="动态规划">动态规划</h3>
<p>根据递归分析，我们已经知道f(n)=2*f(n-1)。因此，可以从f(1)开始，逐步计算f(2), f(3), ..., f(n)，每次利用前一次的结果</p>
<p>动态规划可以将问题分解为重叠的子问题，并存储子问题的解。</p>
<p>初始化：</p>
<ul>
<li>f(1) = 1</li>
<li>递推关系：f(n) = 2 * f(n-1) for n &gt; 1</li>
</ul>
<p>这种方法避免了递归的重复计算，通过迭代方式自底向上构建解</p>
<pre><code class="language-java">public class Solution {
    public int JumpFloorII(int target) {
                if (target &lt;= 0) return 0;
      int[] dp = new int;
      dp = 1;
      for (int i = 2; i &lt;= target; i++) {
            dp = 2 * dp;
      }
      return dp;
    }
}
</code></pre>
<ul>
<li>时间复杂度：O(n)，单层循环</li>
<li>空间复杂度：O(n)，需要dp数组存储中间结果</li>
</ul>
<p>动态规划是递归解法的优化版本，适合大规模输入</p>
<h3 id="优化的动态规划优化空间复杂度">优化的动态规划：优化空间复杂度</h3>
<p>观察动态规划解法，发现计算f(n)只需要前一个状态f(n-1)，不需要保存整个dp数组。因此可以用单个变量代替数组，实时更新当前值。</p>
<p>这种优化基于"滚动数组"思想，只保留必要的中间结果，可以将空间复杂度从O(n)降到O(1)。</p>
<pre><code class="language-java">public class Solution {
    public int JumpFloorII(int target) {
                if (target &lt;= 0) return 0;
      int result = 1;
      for (int i = 2; i &lt;= target; i++) {
            result *= 2;
      }
      return result;
    }
}
</code></pre>
<ul>
<li>时间复杂度：O(n)，单层循环</li>
<li>空间复杂度：O(1)，仅使用常数空间</li>
</ul>
<p>这是最优的迭代解法，应该也是面试官最想要看到的解法。</p>


</div>
<div id="MySignature" role="contentinfo">
    <p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18967803
頁: [1]
查看完整版本: 剑指offer-9-变态跳台阶