洛谷 P1192 台阶问题 题解【递推】

作者: wjyyy 分类: 解题报告,递推 发布时间: 2018-02-21 09:39

点击量:60

– 分析:本题是一个递推的问题,即有n个方案到一个点,那么这个点能到达的点一定有这n个方案。其中加上这一步,方案数没有改变。

– 而且,由不同的点到某一个目标点,方案一定不同,因为这些方案的倒数第二个点不同,所以这些是可以累加的。

– 解决方案:从左向右递推,既然已经扫描到某个点,那么它前面的点一定被扫描过。而一个点的状态只能由它前面的点推过来,所以一直递推到最后。

– 注意事项:这种做法不用特殊处理的话数组要开到[n+k+],因为for循环里的i+j最大就是n+k;最终结果是f[n],后面的数据就不需要了。如果特判i+j<=n的话可能会浪费复杂度为k的时间,所以是要么利用空间的k要么利用时间的k。

– 下面贴代码

#include <cstdio>
#include <cstring>
using namespace std;
int f[100101];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=0;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i+j]+=f[i];
            f[i+j]%=100003;
        }
    printf("%d\n",f[n]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */