算法分析与设计C++ openjudge:台阶问题

#include<stdio.h>
#include<string.h>
long long int dp[1005];
int main()
{
    //K=2
    //1 1
    //2 1
    //3 12 21 111
    //4 211 121 112 22 1111
    //5 2111 1211 1121 1112 122 212 221 1111
	int N,K;
	scanf("%d%d",&N,&K);
    memset(dp,0,N);
    dp[0]=1,dp[1]=1;
    for(int i=1;i<=N;i++){
        if(i<=K){
            dp[i]=1;
            for(int j=2;j<=i;j++){
                dp[i]*=2;
            }
            dp[i]=dp[i]%100003;
        }
        else{
            for(int j=1;j<=K;j++){
                dp[i]+=dp[i-j]%100003;
            }
            dp[i]=dp[i]%100003;
        }
    }
    printf("%lld
",dp[N]);
	return 0;
	}

#include<stdio.h>
#include<string.h>
long long int dp[100005];
int main()
{
    //K=2
    //1 1
    //2 11 2
    //3 12 21 111
    //4 211 121 112 22 1111
    //5 2111 1211 1121 1112 122 212 221 1111
    //k=3
    //1 1
    //2 11 2
    //3 12 21 111 3
    //4 211 121 112 22 1111 13 31
	int N,K;
	scanf("%d%d",&N,&K);
    memset(dp,0,N);
    dp[0]=1,dp[1]=1;
    for(int i=2;i<N;i++){
        dp[i]=0;
        for(int j=0;j<i;j++){
            dp[i]+=dp[j];
        }
    }
    printf("%lld
",dp[N-1]);
	return 0;
}