`

Leetcode - Climbing Stairs

阅读更多

[题目]

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

[分析] 一维动态规划入门题

 

public class Solution {
    // O(n)空间
    public int climbStairs0(int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2]; //递推关系式
        return dp[n];
    }
    
     // O(1)空间
     public int climbStairs(int n) {
        if (n <= 0)
            return 0;
        int[] dp = {1, 1, 1};
        for (int i = 2; i <= n; i++) {
            dp[2] = dp[1] + dp[0];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[2];
     }
}

 

分享到:
评论
1 楼 qb_2008 2015-04-14  
一维dp。

相关推荐

    leetcode走楼梯-LeetCode_70--Climbing-Stairs:LeetCode_70--爬楼梯

    leetcode 走踏板LeetCode_70--爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 说明:...

    leetcode走楼梯-leet-climbing-stairs-70:leet-climbing-stairs-70

    leetcode 走踏板爬楼梯 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。 示例 1: 输入:2 输出:2 解释:有两种方法可以...

    leetcode怎么销号-LeetCode-Solutions:我自己的LeetCode解决方案

    leetcode怎么销号 LeetCode-Solutions :green_heart:My own LeetCode solutions No. Problem LeetCode 力扣 Python Go Solution Difficulty Tag ...Climbing Stairs Easy 动态规划 0075 Sort Colors M

    javalruleetcode-leetcode-java:力码笔记

    70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell Stock II 123.Best Time to Buy and Sell Stock III 141.Linked List Cycle 142.Linked List Cycle II 188.Best Time to ...

    leetcode走楼梯-Climbing-Stairs:Leetcode问题70

    leetcode 走踏板爬楼梯 Leetcode 问题 70 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 示例 1: Input: 2 Output: 2 Explanation: There are two ...

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    Climbing Stairs] [101. Symmetric Tree] [104. Maximum Depth of Binary Tree] [121. Best Time to Buy and Sell Stock] [167. Two Sum II - Input array is sorted] Medium [2. Add Two Numbers]

    leetcode-js:算法和数据结构是一个程序员的灵魂,LeetCode JavaScript TypeScript 题解

    70.爬楼梯 (Climbing Stairs) 83.删除排序链表中的重复元素 (Remove Duplicates from Sorted List) 88.合并两个有序数组 (Merge Sorted Array) 100.相同的树 (Same Tree) 104.二叉树的最大深度 (Maximum Depth of ...

    leetcode走楼梯-Climbing-Stairs:力码练习

    leetcode 走踏板爬楼梯 力码练习 你正在爬楼梯。 需要n步才能到达顶部。 每次您可以爬 1 或 2 个台阶。 你可以通过多少种不同的方式登上顶峰? 注意:给定 n 将是一个正整数。

    LeetCode:Leetcode-解决方案

    Min Cost Climbing Stairs [746]2. Best Time to Buy and Sell Stock [121]3. Climbing Stairs [70]4. Maximum Subarray [53]5. House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. ...

    javalruleetcode-learn-algorithms::laptop:Java实现的各种算法题解

    Stairs](./leetcode/动态规划-Climbing Stairs.java) [动态规划-Decode Ways](./leetcode/动态规划-Decode Ways.java) [动态规划-Distinct Subsequences](./leetcode/动态规划-Distinct Subsequences.java) [动态...

    最大公共字符串leetcode-LeetCodeNotes:LeetCodeNotes包括在LeetCode工作期间的笔记

    Climbing-Stairs 暴力递归,把所有可能的解法递归出来。 public class Sol_one { public int climbStairs(int n) { return climb_Stairs(0, n); } public int climb_Stairs(int i, int n) { if (i &gt; n) { return 0; ...

    leetcode1477-coding-for-fun:编码乐趣

    min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 最长公共子序列.cpp 第 5 天: [待办事项] leetcode/221。 最大平方.cpp 利特代码/85。 最大矩形.cpp 第 6 天: leetcode/97. 交错字符串.cpp ...

    leetcode写题闪退-LeetCode:leetcodeOJ

    leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...

    leetcode答案-LeetCode:Swift中的LeetCode

    leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也包含解出AC 的答案, ...Climbing Stairs Easy #83 Remove Duplicates from Sorted L

    Leetcode扑克-coding-interviews:编码面试

    Leetcode扑克 ...Climbing Stairs 变态跳台阶 矩形覆盖 二进制中1的个数 191. Number of 1 Bits 数值的整数次方 50. Pow(x, n) 调整数组顺序使奇数位于偶数前面 905. Sort Array By Parity 链表中倒数第

    leetcode卡-leetcode:利特码解决方案

    Climbing Stairs Set Matrix Zeroes API System.arrayCopy 刷题顺序 TOP100 其中算法,主要是以下几种: 基础技巧:分治、二分、贪心 排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、深度优先遍历,...

    leetcode答案-LeetCodeSolution:这是LeetCode网站问题的解决方案集

    Climbing Stairs 一开始用传统的递归解题,结果TL了。看了下Dscuss,搜索了一下,发现这道居然就是典型的动态规划题,用哈希把子问题的答案记录了就能节省大量的运行时间。 Linked List Cycle 判断链表是否有环。...

    leetcode482-coding-test:编码测试

    第 482 章编码测试 JewelsAndStones_771 [Java] Java HashMap、ArrayList 包含方法性能对比 LicenseKeyFormatting_482 [Java] String、StringBuffer、StringBuilder 的区别和优缺点 ...ClimbingStairs_70 Q

    leetcode1004-aoj:AOJ

    leetcode 1004 *LC 75problems =&gt; OK/NG =&gt; NG 表示我无法自己解决,所以我应该再次重新访问相同的问题。 OK / NG日期已过级别名称类别NG 20200126全部/所有媒体20200126 20200125_esy_53_maximum_subarray.py OK ...

    leetcode小岛出水口-leetcode:leetcode训练

    Climbing Stairs 0719. Find K-th Smallest Pair Distance 0714. Best Time to Buy and Sell Stock with Transaction Fee 0713. 乘积小于K的子数组 0695. 岛屿的最大面积 0674. 最长连续递增序列 0673. 最长递增子...

Global site tag (gtag.js) - Google Analytics