P1192 台阶问题

P1192 台阶问题

题解

深搜会超时，本题最简单的方法是动态规划。ai给出了记忆化搜索的答案，但是很反直觉。

这里需要令dp[0] = 1 , dp[1] = 1;

#include<iostream>
using namespace std;int cnt ;
int n,k;
long long dp[100010];int main()
{cin>>n>>k;dp[0] = 1;dp[1] = 1;for(int i = 2 ; i <= n ; i++){for(int j = 1 ; j <= k ; j ++){if(i - j < 0) break;dp[i] = (dp[i] + dp[i - j]) % 100003;}}cout<<dp[n] <<endl;return 0;  }