LeetCode【70】Climbing Stairs

 




根据题目找规律,见下表策略选择

        

分析:斐波那契数列的变形

          1 1 2 3 5 8 ……

          本题将第二个数字1换成数字2,形成新的相同算法的数列

          1 2 3 5 8 13 ……


AC代码:

public class Solution {
    public int climbStairs(int n) {
        if(n == 1 || n == 2){
            return n;
        }
        int[] number = new int[n];
        number[0] = 1;
        number[1] = 2;
        for(int i = 2;i<n;i++){
            number[i]= number[i-2]+number[i-1];
        }
        return number[n-1];
    }
}


需要注意:如果先创建数组,会报数组下标溢出的错,如图所示,因为可能输入的n是1,没有办法创建大小为2的数组,先用if判断n的值,再创建数组。



### LeetCode70题 Python 解法 LeetCode70题名为 **Climbing Stairs**,其核心问题是计算到达楼梯顶部的不同方法数。假设每次可以爬 `1` 或 `2` 阶台阶,则可以通过动态规划或者递归来解决此问题。 以下是基于动态规划的解决方案: #### 动态规划解法 通过定义状态转移方程实现: - 设 `dp[i]` 表示到达第 `i` 阶的方法总数。 - 则有状态转移关系: \[ dp[i] = dp[i-1] + dp[i-2] \] 初始条件为: - \( dp[0] = 1 \) (表示停留在地面也算一种方式) - \( dp[1] = 1 \) 最终返回值为 `dp[n]`。 下面是完整的代码实现: ```python class Solution: def climbStairs(self, n: int) -> int: if n == 0 or n == 1: return 1 dp = [0] * (n + 1) dp[0], dp[1] = 1, 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] ``` 上述代码的时间复杂度为 \(O(n)\),空间复杂度也为 \(O(n)\)[^4]。 #### 空间优化版本 由于每一步的状态仅依赖于前两步的结果,因此可以用两个变量代替整个数组存储中间结果,从而进一步降低空间复杂度至 \(O(1)\): ```python class Solution: def climbStairs(self, n: int) -> int: if n == 0 or n == 1: return 1 prev1, prev2 = 1, 1 # 初始化前两步的结果 for _ in range(2, n + 1): current = prev1 + prev2 prev1, prev2 = prev2, current return prev2 ``` 这种方法不仅保持了时间效率,还显著减少了内存占用[^5]。 --- ### 总结 以上两种方法均能有效解决问题,推荐使用第二种优化后的方案以节省资源消耗。对于更复杂的变体题目(如允许更多种跳跃步数),可扩展当前逻辑并调整状态转移方程。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值