JZ71: 跳台阶扩展问题

[songyy5517]

描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

示例1

输入：3
返回值：4

示例2

输入：1
返回值：1

分析 这道题已知初始状态，且当前状态可以由之前的状态推导得到，因此可以使用动态规划来解决。主要注意的是，状态转移方程 $f[i] =f[i-1] + f[i-2] + ... + f[1] + f[0] $ ，而 $f[i - 1] = f[i - 2] + ... + f[0]$ ，因此它可简化为 $f[i] = 2 * f[i - 1]$ 。

[songyy5517]

思路：动态规划

1. 异常处理（n <= 2）；
2. 状态定义 & 初始化；
   • $fi = 2$ ：台阶数i的跳法总数；
   • $res$ : 最终结果 。
3. 自下而上计算各个状态；
   • $res = 2 * fi$ 。
   • 更新变量： $fi = res$ 。
4. 返回最终状态 $res$ 。

复杂度分析

• 时间复杂度： $O(N)$ ，一共要计算N个状态，使用 $O(N)$ 大小的时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

import java.util.*;

public class Solution {
    public int jumpFloorII (int number) {
        // write code here
        if (number <= 2)
            return number;

        int fi = 2, res = 0; 

        for (int i = 3; i <= number; i++){
            res = fi * 2;
            fi = res;
        }

        return res;
    }
}

[songyy5517]

2024/4/30