1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include <vector>

using namespace std;

int calculateNumbers(int);

int main() {
  int num;
  cin >> num;
  cout << calculateNumbers(num);
}

int calculateNumbers(int num) {
  vector<int> listOfDigits;
  while(num > 0) {
    listOfDigits.insert(listOfDigits.begin(), num % 10);
    num /= 10;
  }
  int dp [listOfDigits.size()];
  dp[listOfDigits.size() - 1] = listOfDigits[listOfDigits.size() - 1] + 1;
  for (int i =listOfDigits.size() - 2 ;i >= 0 ;i --) {
      int fromOneNumber = dp[i + 1] * (listOfDigits[i] + 1);
      int fromTwoNumbers = 0;
        int twoDigitNumber = listOfDigits[i] * 10 + listOfDigits[i + 1];
        if (twoDigitNumber <= 18) {
            int num = 19 - twoDigitNumber;
            if (i + 2 > listOfDigits.size() - 1) {
              fromTwoNumbers = num;
            } else {
            fromTwoNumbers = num  * dp[i + 2]; 
            }
        }
        dp[i] = fromOneNumber + fromTwoNumbers;
  }
  return dp[0];
}