[LintCode] Climbing Stairs

jemygraw 發(fā)布于2019-08-14 15:28 / 3059人閱讀

摘要：無需動規(guī)，無需額外空間，等同于菲波那切數(shù)列。當然嚕，也可以動規(guī)，記住就好。

Problem

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?

Example

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3

Note

無需動規(guī)，無需額外空間，等同于菲波那切數(shù)列。
當然嚕，也可以動規(guī)，記住dp[0] = 1就好。

Solution Fibonacci

public class Solution {
    public int climbStairs(int n) {
        if (n < 2) return 1;
        int one = 1, two = 1, total = 0;
        for (int i = 2; i <= n; i++) {
            res = one + two;
            two = one;
            one = res;
        }
        return res;
    }
}

public class Solution {
    public int climbStairs(int n) {
        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];
        return dp[n];
    }
}

云服務器 GPU云服務器 Climbing Stairs LintCode LintCode134_LRU

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65789.html

[LintCode] Climbing Stairs II

Problem A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. Ex...

chengtao1633 2019-08-15 13:32 評論0 收藏0
[Leetcode] Climbing Stairs 爬樓梯

摘要：遞歸法復雜度時間空間思路這題幾乎就是求解斐波那契數(shù)列。最簡單的方法就是遞歸。但重復計算時間復雜度高。代碼遞推法復雜度時間空間思路實際上我們求的時候只需要和的值，所以可以減少一些空間啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

tinyq 2019-08-14 12:26 評論0 收藏0
[leetcode] Climbing Stairs

摘要：實質就是把之前出現(xiàn)過的中間結果記錄，下次再出現(xiàn)相同情況的時候，通過可以只用的時間復雜度得到。表示到達第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

int64 2019-08-14 16:50 評論0 收藏0
746. Min Cost Climbing Stairs

746. Min Cost Climbing Stairs On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find mini...

skinner 2019-07-30 17:08 評論0 收藏0
070. 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? Note: Given n will be a positive i...

jay_tian 2019-07-30 17:09 評論0 收藏0