leetcode70：爬楼梯（climbing-stairs）

[carloscn]

问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 

示例 1：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶  

提示：

1 <= n <= 45

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/climbing-stairs

[carloscn]

同题目，递归法：https://github.com/carloscn/structstudy/issues/44

[carloscn]

问题分析

int32_t claim_stairs(size_t n)
{
    int32_t ret = 0;
    size_t i = 0;
    int32_t dp[3] = {0,1,2};

    switch (n) {
        case 0:
            ret = 0;
            break;
        case 1:
            ret = 1;
            break;
        case 2:
            ret = 2;
            break;
        default:
        // dp(x) = dp(x - 1) + dp(x - 2)
        for (i = 0; i < n; i ++) {
            dp[2] = dp[1] + dp[0];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        ret = dp[2];
        break;
    }

finish:
    return ret;
}

[carloscn]

code

https://github.com/carloscn/structstudy/commit/d2c46e3477ad644842a16caafcb747a69f540768 https://review.gerrithub.io/c/carloscn/structstudy/+/551485