<ul id="ymqei"></ul>

<tfoot id="ymqei"></tfoot>

leetcode70 climbing stairs 爬樓梯游戲

姘存按發布于2019-08-14 17:52 / 912人閱讀

摘要：題目要求假設有級臺階為正整數，每次可以爬一級臺階或兩級臺階。問有多少種方法爬完級臺階遞歸方法最后一步可以是一級臺階，或者是兩級臺階，一共兩種情況。

題目要求：假設有n級臺階（n為正整數），每次可以爬一級臺階或兩級臺階。問有多少種方法爬完n級臺階？

遞歸方法
最后一步可以是一級臺階，或者是兩級臺階，一共兩種情況。可通過遞歸獲得n-1級臺階和n-2級臺階的和獲得n級臺階的結果
臺階數量過高的話，性能會很差

/**
 * @author rale
 * 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 integer.
 */
public class ClimbingStairs {

    //遞歸    
    public int climbStairs(int n) {
        if(n<=1){
            return 1;
        }
        if(n%2==0){
            return (int) (Math.pow(climbStairs(n/2), 2)+Math.pow(climbStairs(n/2-1), 2));
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

非遞歸情況
為了提高性能，將遞歸轉化為循環
可以將題目轉換為n級臺階中有幾步是爬了兩級臺階，幾步是爬了一級臺階
例如 3級臺階的的場景為 3個一步或者 1個一步加1個兩步
則n級臺階的場景為：
假設n級臺階中有a個兩步，n-2*a個一步，則情況總數為C(n-a,a)
a的取值范圍為[0,n/2]

/**
 * @author rale
 * 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 integer.
 */
public class ClimbingStairs {
        public int climbStairs(int n){
        if(n<=1){
            return 1;
        }
        int countTwo = 1;
        int total = 1;
        while(countTwo*2<=n){
            //此處應設為long，防止值溢出
            long temp = 1;
            for(int i = n-countTwo, j = 1 ; j<=countTwo; i--,j++){
                temp = temp*i/j;
            }
            total += temp;
            countTwo++;
        }
        return total;
    }
}

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器爬樓梯 Climbing Stairs 樓梯

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

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

LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

摘要：小鹿題目假設你正在爬樓梯。需要階你才能到達樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個正整數。算法思路二種解決思路，第一利用遞歸第二利用動態規劃。就是因為有了重復元素的計算，導致了時間復雜度成指數的增長。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿題目：Climbing Stairs You a...

chemzqm 2019-08-23 16:55 評論0 收藏0
[Leetcode] Climbing Stairs 爬樓梯

摘要：遞歸法復雜度時間空間思路這題幾乎就是求解斐波那契數列。最簡單的方法就是遞歸。但重復計算時間復雜度高。代碼遞推法復雜度時間空間思路實際上我們求的時候只需要和的值，所以可以減少一些空間啊。 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

摘要：實質就是把之前出現過的中間結果記錄，下次再出現相同情況的時候，通過可以只用的時間復雜度得到。表示到達第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個，和。 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
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
leetcode 746 Min Cost Climbing Stairs

摘要：同時你可以選擇從第階開始或者第一階開始。我們的目標是找出你爬到最頂層所付出的最小的開銷。最低開銷是，從第階開始，只花費就可以到頂層。想法動態規劃問題。的長度應該為數組長度加一，其中數組的最后一個元素的值就是本題的答案，最低開銷。題目詳情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...

fyber 2019-08-16 11:01 評論0 收藏0