【DidaOJ】[1134]感恩节KK专场——爬楼梯

问题描述

问题分析

题目虽然T数据是10000，但是n数据其实只有30，这也提示了最好使用打表法来构造数据。

可以比较容易地发现，如果使用$ dp[i] $来表示爬到第$i$层楼梯的方案数，那么可以得到递推式：

$$ dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] $$

也即爬到第$i$层楼梯的方案数等于爬到第$i-1$层楼梯的方案数加上爬到第$i-2$层楼梯的方案数加上爬到第$i-3$层楼梯的方案数。

需要注意的是样例中指出n = 1的情况下需要输出0，但是在递推的时候很显然到第一层也需要视为一种方案，所以$dp[1]$需要初始化为$1$，在输出时需要特判。

AC代码

cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

int dp[32];

int main()
{
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    for (int i = 4; i < 32; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }

    int T;
    std::cin >> T;
    while (T--)
    {
        int n;
        std::cin >> n;
        if (n <= 1)
        {
            std::cout << 0 << std::endl;
        }
        else
        {
            std::cout << dp[n] << std::endl;
        }
    }
    return 0;
}

题目地址：感恩节KK专场——爬楼梯 - 问题详情 - 题目 - DidaOJ