- it
- 算法分析与设计C++ openjudge:台阶问题
#include<stdio.h>
#include<string.h>
long long int dp
[1005];
int main()
{
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\n",dp
[N
]);
return 0;
}
#include<stdio.h>
#include<string.h>
long long int dp
[100005];
int main()
{
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\n",dp
[N
-1]);
return 0;
}
