leetcode

0 class Solution {

1 static const int mod = 1E9 + 7;

2 static const int size = 1E5 + 1;

3 int dp[size];

4

5 public:

6 Solution() { memset(dp, 0xFF, sizeof(dp)); }

7

8 int numberOfArrays(const string &s, int k, int crnt = 0) {

9 if (crnt >= s.size()) return 1;

10 if (s[crnt] == '0') return 0;

11 if (dp[crnt] != -1) return dp[crnt];

12

13 long long num = 0, res = 0;

14 for (int i = crnt; i < s.size(); i++) {

15 num = num * 10 + (s[i] - '0');

16 if (num > k) break;

17 res = (res + numberOfArrays(s, k, i + 1)) % mod;

18 }

19

20 return dp[crnt] = res;

21 }

22 };