Leetcode-070-爬楼梯

Leecode-070-Climbing Stairs

思路：动态规划

题目描述

每次爬楼梯可以爬1个或者2个台阶，你有多少种不同的方法可以爬到楼顶？

注意：给定的n是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

Solution：

• 第 i 阶可以由以下两种方法得到：
  • 在第 (i−1) 阶后向上爬一阶。
  • 在第(i−2) 阶后向上爬 22 阶。

所以到达第 i 阶的方法总数就是到第(i−1) 阶和第 (i−2) 阶的方法数之和。

令 dp[i]表示能到达第 i 阶的方法总数：

​ dp[i]=dp[i−1]+dp[i−2]

例如：6级台阶是由5级和4级台阶构成

Java

Solution :

class Solution{
    public int climbStairs(int n){
        // 初始化(长度为 n+1 的原因是 有0索引的存在)
        int[] dp = new int[n + 1];

        dp[0] = 1;
        dp[1] = 1;

        // 状态转移
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回第n个台阶有多少种爬法
        return dp[n];
    }
}

• 时间复杂度：O(n) 遍历n次。
• 空间复杂度：O(n)使用了一个dp数组存储元素。

Python

Solution :

打赏