程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 70 Climbing Stairs(爬樓梯)(動態規劃)(*)

LeetCode 70 Climbing Stairs(爬樓梯)(動態規劃)(*)

編輯:C++入門知識

LeetCode 70 Climbing Stairs(爬樓梯)(動態規劃)(*)


翻譯

你正在爬一個樓梯。它需要n步才能到底頂部。

每次你可以爬1步或者2兩步。

那麼你有多少種不同的方法爬到頂部呢?

原文

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?

分析

動態規劃基礎題,首先設置3個變量用於轉換:

int dp1 = 1, dp2 = 2, dpWay = 0;

根據題意,一次只能是一步或兩步,所以當n等於2時,有兩種走法:1+1,2。

if (n <= 1) return dp1;
if (n == 2) return dp2;

從3開始,因為可以直接獲得它的步數結果,所以直接寫成:

while ((n--)-2) {
}

最終裡面的變化方式為:

dpWay = dp1 + dp2;
dp1 = dp2;
dp2 = dpWay;
int climbStairsIter(int n,  int dpWay,int dp1, int dp2) {
    if (n <= 1) return dp1;
    if (n == 2) return dp2;
    if ((n--) - 2) {
        dpWay = dp1 + dp2;
        dp1 = dp2;
        dp2 = dpWay;
        return climbStairsIter(n, dpWay, dp1, dp2);
    }
    else return dpWay;
}

int climbStairs(int n) {
    return climbStairsIter(n, 0,1,2);
}

因為這裡的參數涉及到執行前面順序,所以最好還是單獨列出來了,不過這樣看來略不簡潔吶。

代碼

class Solution {
public:
    int climbStairs(int n) {

        int dp1 = 1, dp2 = 2, dpWay = 0;
        if (n <= 1) return dp1;
        if (n == 2) return dp2;

        while ((n--) - 2) {
            dpWay = dp1 + dp2;
            dp1 = dp2;
            dp2 = dpWay;
        }
        return dpWay;
    }
};
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved