[每日算法]台阶问题

题目描述

有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少11级），问到达第NN级台阶有多少种不同方式。

输入格式

两个正整数N，K。

输出格式

一个正整数，为不同方式数，由于答案可能很大，你需要输出ans mod 100003后的结果。

输入输出样例

样例#1	输出#1
5 2	8
98765 89	86214

说明/提示

对于20%的数据,有N ≤ 10, K≤3;

对于40%的数据，有N≤1000;

对于100%的数据，有N ≤ 100000,K ≤ 100。

题解

根据N与K的值，列举一些具体的答案。

横坐标为总台阶数N，纵坐标为每次能走的最大步数K。

	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2	1	2	3	5	8	13	21	34
3	1	2	4	7	13	24	44	81
4	1	2	4	8	15	29	56	108
5	1	2	4	8	16	31	61	120

通过观察可以发现这个问题其实是一个变相的斐波那契数列。

解法1

用递归的思想来做，假设因为最大的步数为K，楼梯步数为N时的走法有a_N种，那么最后走1步时，这步之前的走法有a_N-1种；最后走2步时，这步之前的走法有a_N-2种….最后走K步时，这步之前有a这步之前的走法有a_N-K种，所以说楼梯步数为N时的走法数量为a_N-1+a_N-2+…+a_N-K。
因此只需要根据最大的步数K将阶梯数为1，2…K的总数分别写下来，即先初始化斐波那契数列前面的K项，接下来的项数只需要将前K项相加得到该项的总数。经过观察可以发现前面K项是有一个首项为1，公比为2的等比数列。因此程序先使用一个for循环将前K项初始化，由于加数的个数为K是个变量，这时候需要一个双重循环重置K项以后的项，第一重循环为处理的第i项，第二重循环是分别加这项前面的N项。返回最后一项的结果即可，时间复杂度为O(NK)。

解法2

解法1虽然思路比较清晰，但是代码实现相对麻烦一点，时间复杂度也比较大，通过整理解法1的数学公式，稍加推导就可以得到简化的公式：
当K=1时，无论台阶数有多少，都只能一次走一步，因此只有一种走法。

当K≠1，发现当i≤K时，有a_i=2a_i-1（即当前项为前一项的两倍）;
i＞K时，有a_i=a_N-1+a_N-2+…+a_N-K=2a_i-1-a_i-1-K
与解法1相比，只需要初始化第一项为1，接下来只需要执行循环，如果i≤K，就为前一项的2倍，如果i＞K，就为前一项的倍减去第i-1*-K项。返回最后一步的结果即可，时间复杂度为O(n)。

解法2源代码

#include <iostream>
using namespace std;

int main()
{
    //获取台阶的级数N和最大的步数K
    int N, K;
    int i = 0;
    cin >> N >> K;
    //为结果创建一个大小为N的动态数组
    int* result = new int[N];
    if (N < 1 || K < 1)
    {//先检查输入的数是否合法
        cout << "请输入大于0的整数!" << endl;
        return 0;
    }

    //初始化第0项和第一项为0
    result[0] = result[1] = 1;

    if (K == 1)
    {如果最大步数为1，那么级数为多少结果都为1
        cout << "1" << endl;
        return 0;
    }

    //注意避免出现负数,结果的数字可能比较大，需要mod100003
    for (i = 2;i <= N;i++)
    {
        if (i <= K)
        {//i<=K时为前一项的两倍
            result[i] = (2 * result[i - 1]) % 100003;
        }
        else
        {//i>K时为前一项的两倍减去第i-1-K项
            result[i] = (2 * result[i - 1]-result[i-1-K]) % 100003;
        }
    }

    cout << (result[N]+100003)%100003 << endl;

    return 0;
}