Advertisement
Josif_tepe

Untitled

Apr 10th, 2022
1,023
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. const int MOD = 1e9 + 7;
  8. int n;
  9. int dp[1000005];
  10. int rec(int suma) {
  11.     if(suma == n) {
  12.         return 1;
  13.     }
  14.     if(dp[suma] != -1) {
  15.         return dp[suma];
  16.     }
  17.     int result = 0;
  18.     for(int i = 1; i <= 6; i++) {
  19.         if(suma + i <= n) {
  20.             result += rec(suma + i);
  21.             result %= MOD;
  22.         }
  23.     }
  24.     return dp[suma] = result;
  25. }
  26. int main() {
  27.     memset(dp, -1, sizeof dp);
  28.     cin >> n;
  29.     cout << rec(0) << endl;
  30.     return 0;
  31. }
  32. // rec(0) = rec(1) + rec(2) + rec(3) = 2 + 1 + 1 = 4
  33. // rec(1) = rec(2) + rec(3) = 1 + 1 = 2
  34. // rec(2) = rec(3) = 1
  35. // rec(3) = 1
  36.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement