题解 P1192 【台阶问题】

· · 题解

P1192 【台阶问题】

好吧我承认这道题确实是 水

但是我还是忍不住成为最详细的题解。

先把题目copy过来

题目描述

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

输入格式

两个正整数N，K。

输出格式

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

输入输出样例

输入 5 2 输出 #1 复制 8 说明/提示 对于20\%20%的数据,有N ≤ 10, K ≤ 3；

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

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

在这里我介绍两种方法，其实是因为实在想不出其他方法了

首先看到这道题目索性先找找规律，然后没想到... 用这种方法AC以后的我非常的不甘心，于是发现这道题正解是DP（难道不应该想象到DP吗？） 于是就有了这两种方法，接下来我会详细解释两种方法的。 orzorzorz

方法一：

这种方法已经是很多dalao用过的方法了，我前面也已经有写到过，就是找规律。 很多人会问这道题有什么规律，我写出来你自然就明白了了！

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

大家如果仔细观察，发现k=2时前两项是1,2； k=3时前三项是1,2,4；以此类推，发现k=n的话，前n项就是等差数列。其中公差是2； 于是乎顺着这个思路我们不难发现隐藏其中的规律...

规律： 
当n<=k时,第N项=(上一项*2)%100003;
当n>k时 ,第N项=(上一项*2-第n-1-k项)%100003;

于是写到这里（已经没法在详细了）这道题就变成了一道极水无比的小学数学题（虽然我小学数学很垃圾）

为了方便你们复制代码，我没有在代码里面加注释。

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=100003;
int n,k,a[1000000],ans=0;
int main()
{
    cin>>n>>k;
    a[0]=a[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(i<=k)
        {
            a[i]=(a[i-1]*2)%mod;
        }
        else 
        {
            a[i]=(a[i-1]*2-a[i-k-1])%mod;
        }
    }
    ans=(a[n]+mod)%mod;
    cout<<ans;
    return 0;
}
  //华丽结束

所以说以上就是第一种方法。

方法二：

正解来了，其实很多像我一样的大佬首先肯定想到这就是dp的板子！ 于是按照这个板子，就不难想到第二种思路，由于考虑到你们不喜欢看许多文字，只喜欢代码 我给你们贴心的写出了伪代码！

台阶问题：
输入：n、k
dp[i]----表示到达当前台阶得方式总和
dp[0]=1;
dp[1]=1;
for(i:2~n)
{//遍历所有台阶
   for(j:1~k)
    {
        if i-j?0
        dp[i]=(dp[i]+dp[i-j])%100003
    }
}
cout<<dp[n]；

以上的伪代码其实写的比较明白，首先要明白dp[i]表示的是到达当前台阶得方式总和，但是其中不要忘记把一二级都初始化成为1。由于结果比较大，一定不要忘记边走边模！

有了以上一点微弱的分析，我们就可以按照伪代码写出你们想要的真正代码！

#include<iostream>
#include<cstdio>
using namespace std;
const int mod=100003;
int n,k,dp[1000000];
int main()
{
    cin>>n>>k;
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i>=j)
            {
                dp[i]=(dp[i]+dp[i-j])%mod;
            }
        }
    }
    cout<<dp[n]%mod;
    return 0;
}

相信到这里，看完我详细的解释，你已经有一些思路，如果没看懂，欢迎私信。

不要忘记康康我的博客。