台阶问题_牛客博客

台阶问题

分析
$第一眼看到这题的时候就直接想用 D f s 模拟走路的过程，可是发现 n 数据范围为 1 e 5 ，就计算一下复杂度。接近 O （ 2^{n} ）$
$无非就是 t l e 。但是为了练习我的 d f s 模板，于是我就手打一遍 T l e 的 d f s ，代码如下$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll cnt=0,n,k,p=100003;
void dfs(ll num){
	if(num==n) {cnt++;cnt=cnt%p;return ;}
	if(num>n) return ;
	for(int i=1;i<=k;i++){
		dfs(num+i);
	}
	return;
}
int main(){
    scanf("%lld%lld",&n,&k);
    dfs(0);
    cout<<cnt<<endl;
    return 0;
}
///dfs的复杂度是2^n tle

$接下来，我就想用什么来优化 d f s 呢？ d p 突然出现在我的脑海里面，分析一波 d p 可用性，发现符合最小子问题$
$于是，我就假设初始位置为 j, 目标位置为 i ，那么 d p [d i s] 表示走到 d i s 的时候所用的所有可能方式。我们接下来考虑$
$怎样从 j 转移到 i 位置呢？$
$从 j 位置走到 i 位置，分 j = i - k, i - (k - 1), i - (k - 2), . . . . . ., i - 1 这些位置走一步到达，那么我们就可以利用循环来更新 d p [i]$

for(int i=1;i<=n;i++){
    for(int j=1;j<=k;j++){/判断条件需要修改，这里只是为了说明怎么走
        dp[i]=dp[i]+dp[i-j];
    }
}

$细心的你可以发现当 i 小与等于 k 的时候会出现错误。没错，就是这样，这里我们就可以在上面的判断条件中改一下$
$把 j < = k$ 改成j<=k&&i-j>=0

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,k,p=100003,dp[maxn];
int main(){
    scanf("%d%d",&n,&k);
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;i++){
    for(int j=1;j<=k&&i-j>=0;j++){
        dp[i]=(dp[i]+dp[i-j])%p;
    }
    }
    cout<<dp[n]<<endl;
    return 0;
}