DP Intuition - visual explanation
Consider we have a tree and each node can have two children i.e. you can extend it with 0 or 1. Initially we have a dummy node(x).\n\n1. Process one character a
Consider we have a tree and each node can have two children i.e. you can extend it with 0 or 1. Initially we have a dummy node(x).\n\n1. Process one character at a time\n2. Figure out which all nodes can be extended with current character\n3. Store only the delta at current location\n\nInput: 111001\n\n1. process 1. We only have a dummy node and only one edge can be formed here, so count = 1\n2. process 1. We have one dummy node but it is already extended in previous step. We\'re only left with previous node and we can only extend it. count = 1\n3. process 1. Same as above. count = 1\n4. process 0. This is the first time 0 is coming. We can extend all nodes with 0 since no one has any edge with 0. count = 4\n5. process 0. Previous step extended all previous steps. We can only extend previous step 0 ends. There is only one exception since we can\'t extend 0 prefix. count = 3\n6. process 1. We have 3 characters which need extension. Before this, we already covered everything(find last one\'s occurrence). count = 1+3(we can\'t extend 0)+3 = 7\n7. To get the answer -> add all these counts\n\n**The reason why we\'re not adding to all existing edges is to avoid duplication**\n\n![image](https://assets.leetcode.com/users/images/440d9dfe-5a35-48f0-8d31-0758fda69dfa_1630213356.109798.png)\n\n\nTo implement this we have a count array which would contain data of only delta counters which are new by including current character. We try to find the last character which needs some extension and add all delta upto current character. In this process, we need to check about edge case when 0 can be extended.\n\n```\nclass Solution {\n    private static final int MOD = 1_000_000_007;\n    \n    public int numberOfUniqueGoodSubsequences(String binary) {\n        int[] count = new int[binary.length()];\n        \n        int[] occurrence = new int[2];\n        int[] lastPosition = new int[] {-1, -1};\n        \n        int firstZeroLoc = -1;\n        \n        for (int i = 0; i < binary.length(); i++) {\n            int idx = binary.charAt(i) - \'0\';\n            if (firstZeroLoc == -1 && binary.charAt(i) == \'0\') {\n                firstZeroLoc = i;\n            }\n            \n            if (i == 0) {\n                occurrence[idx]++;\n                lastPosition[idx] = 0;\n                count[0] = 1;\n                continue;\n            }\n            \n            long sum = 0;\n            \n            if (occurrence[idx] == 0) {\n                sum++;\n            }\n            \n            int start = Math.max(0, lastPosition[idx]);\n            sum += getSum(count, start, i, firstZeroLoc);\n            sum %= MOD;\n            \n            lastPosition[idx] = i;\n            occurrence[idx]++;\n            count[i] = (int) sum;\n        }\n        \n        long ans = 0;\n        for (int i = 0; i < binary.length(); i++) {\n            ans += count[i];\n            ans %= MOD;\n        }\n        return (int) ans;\n    }\n    \n    private int getSum(int[] count, int start, int end, int firstZeroLoc) {\n        long sum = 0;\n        for (int i = start; i < end; i++) {\n            if (i == firstZeroLoc) {\n                if (count[i] - 1 == 0) {\n                    sum += MOD;\n                } else {\n                    sum += count[i] - 1;\n                }\n\n            } else {\n                sum += count[i];\n            }\n            sum %= MOD;\n        }\n        return (int) sum;\n    }\n}\n```
['Dynamic Programming', 'Java']