剑指offer-8、跳台阶
<h2 id="题">题⽬</h2><p>⼀只⻘蛙⼀次可以跳上1级台阶，也可以跳上2级。求该⻘蛙跳上⼀个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。</p>
<p>示例1<br>
输⼊：2<br>
输出：2<br>
解释：⻘蛙要跳上两级台阶有两种跳法，分别是：先跳⼀级，再跳⼀级或者直接跳两级。因此答案为2</p>
<p>示例2<br>
输⼊：7<br>
输出：21</p>
<p>示例3：<br>
输⼊：0<br>
输出：0</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="动态规划">动态规划</h3>
<p>这题和第7题 斐波那契数列 基本类似，只是换了一个题目表达方式。</p>
<p>青蛙跳到第<code>n</code>级台阶的跳法数 dp 取决于两种最后一步的选择：</p>
<ul>
<li>从第<code>i-1</code>级跳1级：跳法数为 dp</li>
<li>从第<code>i-2</code>级跳2级：跳法数为 dp</li>
</ul>
<p>使用数组 <code>dp</code>，其中 <code>dp</code> 表示跳到第 <code>i</code> 级台阶的跳法数</p>
<p><strong>状态转移</strong>：<code>dp = dp + dp</code>，初始化 <code>dp = 1</code>，<code>dp = 2</code></p>
<pre><code class="language-java">public intrectCover(int target){
if target <= 2{
return n
}
int[] dp = new int;
int dp = 1;
int dp = 2;
for (int i = 3; i <= target; i++) {
dp = dp + dp;
}
return dp
}
</code></pre>
<ul>
<li>时间复杂度 <code>O(n)</code></li>
<li>空间复杂度 <code>O(n)</code></li>
</ul>
<h3 id="动态规划滚动数组优化">动态规划（滚动数组优化）</h3>
<p>观察状态转移方程，发现当前状态仅依赖前两个状态（<code>dp</code> 和 <code>dp</code>），因此只需保存这两个值，无需存储整个数组</p>
<pre><code class="language-java">public class Solution {
public int rectCover(int target) {
if (target <= 0) {
return 0;
}
if (target < 3) {
return target;
}
int num1 = 1; // 代表 dp
int num2 = 2; // 代表 dp
int result = 0;
for (int i = 3; i <= target; i++) {
result = num1 + num2;
//更新前两项
num1 = num2;
num2 = result;
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度 <code>O(n)</code></li>
<li>空间复杂度 <code>O(1)</code></li>
</ul>
<h3 id="如何思考空间优化方法">如何思考空间优化方法？</h3>
<ol>
<li><strong>观察状态依赖</strong>： 确认当前状态是否仅依赖有限的前几个状态（如斐波那契数列仅依赖前两项）</li>
<li><strong>变量替换</strong>： 用固定数量的变量替代数组，滚动更新这些变量</li>
<li><strong>边界处理</strong>： 初始化时需明确前几个状态的初始值（如 <code>f(1)</code> 和 <code>f(2)</code>）</li>
</ol>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18953427
頁:
[1]