Simon in the boss

class Solution {
    #define Mod (int)(1e9+7)
    #define Max 3505
public:
    bool dpVisited[Max][Max], compareVisited[Max][Max];
    int dp[Max][Max], length;
    short compare[Max][Max];
    string str;

    // This compares the same length string that starts at position pre
    // and string that starts at cur.
    // If it returns -1 that means strings of same length starting from cur
    // are always bigger (or equal to) than string of the same length starting from pre.
    // if it returns a nonnegative number ret, that means we can only go ret distance
    // from pre and cur , after that pre becomes bigger than cur.
    int compareFunc(int pre, int cur){
        if(cur == length) return -1;
        if(compareVisited[pre][cur])
            return compare[pre][cur];
        
        compareVisited[pre][cur] = true;
        
        if(str[pre] != str[cur]){
            if(str[cur] > str[pre]) return compare[pre][cur] = -1;
            return compare[pre][cur] = 0;

        }
        int val = compareFunc(pre + 1, cur +1);
        if(val == -1) return compare[pre][cur] = -1;
        return compare[pre][cur] = val + 1;
    }

    // This counts the number of result where current number starts at pos
    // and the last number was of length len.
    int dpFunc(int pos, int len){

        if(pos > length) return 0;
        if(pos == length) return 1;

        if(dpVisited[pos][len])
            return dp[pos][len];
        
        dpVisited[pos][len] = true;

        int ret = dpFunc(pos+1, len +1);

        if(str[pos]=='0' || pos+len > length)
            return dp[pos][len] = ret;

        int curLen = len + 1;
        int val = compareFunc(pos-len, pos);

        if(val ==-1 || val >=len)
            curLen--;
        
        if(pos + curLen > length)
            return dp[pos][len] = ret;
        
        ret = (ret + dpFunc(pos + curLen, curLen) )%Mod;

        return dp[pos][len] = ret;

    }
    int numberOfCombinations(string num) {
        str = num;
        length = str.length();

        if(str[0] =='0') return 0;

        return dpFunc(1,1);
        
    }
};