Advertisement
Guest User

Stairs with Extra Steps

a guest
Oct 8th, 2019
537
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ok puts("ok")
  5. #define ll long long
  6. #define pb push_back
  7. #define mk make_pair
  8. #define fr first
  9. #define sc second
  10. #define vi vector < int >
  11. #define pi pair < int, int >
  12.  
  13. const int N = 3e5 + 7;
  14. const int mod = 1e9 + 7;
  15.  
  16. ll dp[N][30];
  17. int A, B;
  18.  
  19. ll top_down(int stair, int triple){
  20.     if (stair == 0)
  21.         return 1;
  22.     if (stair < 0)
  23.         return 0;
  24.     if (dp[stair][triple])
  25.         return dp[stair][triple];
  26.     if (triple)
  27.         dp[stair][triple] = top_down(stair - 3, triple - 1);
  28.     dp[stair][triple] += top_down(stair - 1, triple) + top_down(stair - 2, triple);
  29.     return dp[stair][triple] % mod;
  30. }
  31.  
  32. main(){
  33.     scanf("%d%d", &A, &B);
  34.     printf("%lld", top_down(A, B));
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement