当前位置: 代码迷 >> 综合 >> 递推 洛谷 P1192 台阶问题
  详细解决方案

递推 洛谷 P1192 台阶问题

热度:5   发布时间:2024-01-15 08:41:25.0

题目描述

有N级的台阶,你一开始在底部,每次可以向上迈最多K级台阶(最少1级),问到达第N级台阶有多少种不同方式。

输入输出格式

输入格式:

输入文件的仅包含两个正整数N,K。

输出格式:

输入文件stair.out仅包括1个正整数,为不同方式数,由于答案可能很大,你需要输出mod 100003后的结果。

输入输出样例

输入样例#1: 复制

5 2

输出样例#1: 复制

8

说明

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

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

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

题目分析:

递推很经典的题目(但我感觉仍然是动态规划),我们设f[i]为到i的路的种类,则我们只能由f[i-k],f[i-k+1]…….f[i-1]到达,k为步数。

所以得到递推式:f[i]+=f[i-j](i-j>0,1<=j<=k)

边界条件:f[0]=1

实现代码:

 

#include <bits/stdc++.h>
using namespace std;int n,i,m,j;int f[100005];
int main()
{cin>>n>>m;memset(f,0,sizeof(f));f[0]=1;                 //很重要的初始化for(i=1;i<=n;i++)      //枚举楼梯{for(j=1;j<=m;j++)   //枚举可能的步数if(i-j>=0)    f[i]+=f[i-j];f[i]%=100003;}cout<<f[n];return 0;
}


  相关解决方案