[C++] Memorization | Recurssion
Below is the three obervation we have to see\nThree Observations:\n1. String can\'t start from zero(except only 0), so our string will always start from 1\n2. S
Below is the three obervation we have to see\nThree Observations:\n1. String can\'t start from zero(except only 0), so our string will always start from 1\n2. String starting from \'1\' will always cover all the good string which can be formed from any one choosen afer this one . For example "100100" \nAll  unique good string starting from 0th position = [1, 10, 100, 11, 101, 1010, 10100, 1001, 10010, 100100, 110, 1100, 1000, 100000]\nAll  unique good string starting from 3th position = [1, 10, 100]\nif we see unique good string staring from 0th position covers all unique good string 3rd position i.e we only need to calculate for the first position of \'1\' only\n3. If string contains zero than we can +1 the total string count ( "0" is valid string)\n\nBelow is my contest code\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> o_z;\n    vector<long long> memo;\n    long long MOD = 1e9 + 7;\n    long long solve(int pos, int &n) {\n        if (pos >= n) return 0;\n        long long &ret = memo[pos];\n        if (ret != -1) return ret;\n        ret = 1; // string ending at this position\n        ret +=solve(o_z[pos][0], n); // for next position we can choose zero\n        ret %= MOD;\n        ret += solve(o_z[pos][1], n); // for next position we can choose one\n        return ret % MOD;\n        \n        \n    }\n    int numberOfUniqueGoodSubsequences(string binary) {\n        int n = binary.size();\n        memo.resize(n + 1, -1);\n        o_z.resize(n, vector<int>(2, 0));\n        o_z[n-1][0] = o_z[n-1][1] = n + 1;\n        int last_one = n + 1, last_zero = n + 1;\n        if (binary[n-1] == \'0\') last_zero = n - 1;\n        else last_one = n - 1;\n        for (int i = n - 2; i >= 0; i--) {\n            o_z[i][0] = last_zero;\n            o_z[i][1] = last_one;\n            if (binary[i] == \'0\') last_zero = i;\n            else last_one = i;\n        }\n        long long ret = solve(last_one, n);\n        if (last_zero < n) ret += 1;\n        return ret % MOD;\n        \n    }\n};\n```\n\n
['Recursion', 'Memoization', 'C']