Advertisement
Josif_tepe

Untitled

Mar 19th, 2021
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.65 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. string s;
  5. int memo[255];
  6. int f(int x) {
  7.     if(x >= s.length()) {
  8.         return 1;
  9.     }
  10.     if(memo[x] != -1) {
  11.         return memo[x];
  12.     }
  13.     int ways = 0;
  14.     if(s[x] != '0') {
  15.         ways += f(x + 1);
  16.     }
  17.     if(s[x] != '0' and x + 1 < s.length()) {
  18.         int number = (s[x] - '0') * 10 + (s[x + 1] - '0');
  19.         if(number <= 26) {
  20.             ways += f(x + 2);
  21.         }
  22.     }
  23.     memo[x] = ways;
  24.     return memo[x];
  25. }
  26. int main()
  27. {
  28.     cin >> s;
  29.     for(int i = 0; i <= s.length(); i++) {
  30.         memo[i] = -1;
  31.     }
  32.     cout << f(0) << endl;
  33.     return 0;
  34. }
  35.  
  36. // 2504
  37.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement