Leetcode-70Climbing Stairs

70. 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 integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

题解：

每次可以爬1或2阶台阶，求n阶台阶有多少种上楼方法；
原问题：n阶台阶的上楼方法
子问题：
1阶台阶上楼方法：dp[1] = 1;
2阶台阶上楼方法：dp[2] = 2;
3阶台阶上楼方法：从1阶跳两步或从2阶跳一步：dp[3] = dp[1] + dp[2];
确认状态：
n阶台阶可以从n-2阶跳两步或者从n-1阶跳一步；从n-2阶跳两步的方法有dp[n-2]种，从n-1阶跳一步的方法有dp[n-1]种；
所以得到动态规划转移方程：dp[n] = dp[n-1] + dp[n-2]; 边界状态：dp[1] = 1; dp[2] = 2;

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 3, 0);  //创建一个包含 n + 3 个 整数 0 的 vector 数组；
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

int main() {
    Solution s;
    printf(" 5 阶楼梯有 %d 种上楼方式", s.climbStairs(5));
    return 0;
}

结果：

 5 阶楼梯有 8 种上楼方式

My Solution 1(Python)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0]
        dp.append(1)
        dp.append(2)
        for i in range(3, n + 1):
            dp.append(dp[i - 1] + dp[i - 2])
        return dp[n]

My Solution 2(Python)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        num2 = n // 2
        sum = 1
        count = 1
        for i in range(1, num2 + 1):         # 2最多有 num2 个
            time = 1
            for num1 in range(n - 2 * i + 1, n - i + 1):
                count = count * num1 // time
                time += 1
            sum = sum + count
            count = 1
        return sum

Reference:

def climbStairs(self, n):
    a = b = 1
    for _ in range(n):
        a, b = b, a + b
    return a