java dp
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int numberOfUniqueGoodSubsequences(String binary) {\n\n        // 0 \uC774 lead \uD558\uBA74 \uC548\uB41C\uB2E4. \n        // 1. dp[n][2] , 0 \uB610\uB294 1\uB85C \uB05D\uB098\uB294 \uAC12\uC744 \uC800\uC7A5\n        \n        // 2. \uCD5C\uCD08 1\uC774 \uBC1C\uC0DD\uD558\uAE30 \uC804\uAE4C\uC9C0 dp[i]\uB294 \uAC74\uB108 \uB6F4\uB2E4. \n        //    1\uC774 \uBC1C\uC0DD\uD558\uBA74 dp[i][1] \uC5D0 1\uC744 \uB123\uC5B4\uC900\uB2E4. \n        \n        // 3 .1\uC774 \uBC1C\uC0DD\uD55C \uD6C4\uC5D0\uB294 \n        //    \uC774\uC804\uC5D0 \uBC1C\uC0DD\uD55C \uAC12\uB4E4\uC744 \uC774\uC6A9\uD574 \uC0C8\uB85C\uC6B4 subsequence\uB97C \uB9CC\uB4E4\uC5B4\uC8FC\uACE0 \uAE30\uC874 \uAC12\uB4E4\uC744 \uC778\uACC4\uD574\uC900\uB2E4. \n        //    1) s.charAt(i) == 0 \uC77C \uB54C \n        //            dp[i][0] += dp[i-1][0]+ dp[i-1][1];\n        //            dp[i][1] += dp[i-1][1];\n        //   2)  s.charAt(i) == 1 \uC77C \uB54C \n        //            dp[i][1] += dp[i-1][0]+ dp[i-1][1]+1;\n        //            dp[i][0] += dp[i-1][0];\n        //        \u203B 1\uC740 leading\uC774 \uAC00\uB2A5\uD558\uAE30 \uB54C\uBB38\uC5D0 1 \uD558\uB098\uB9CC \uC788\uB294 sequence\uB97C \uC720\uC9C0\uD558\uAE30 \uC704\uD574 1\uC744 \uB354 \uB354\uD574\uC900\uB2E4. \n\n        // 101\n\n        // dp[0][] : []  [1]  \n\n        // dp[1][] : [10] [1]\n\n        // dp[2][] : [10]  [101 11 1]   0\uC774 \uD558\uB098\uB77C\uB3C4 \uC788\uC5C8\uC73C\uBBC0\uB85C [0] \uD3EC\uD568 \uCD1D 5\uAC1C\n\n        // 4. dp[n-1][0]+dp[n-1][1] \uBC18\uD658   \u203B 0\uC774 \uD558\uB098\uB77C\uB3C4 \uBC1C\uC0DD\uD588\uC73C\uBA74 subsequence 0 \uC774 \uD3EC\uD568\uC774 \uB418\uC5B4\uC57C\uD558\uBBC0\uB85C 1\uC744 \uCD94\uAC00\uB85C \uB354\uD574\uC900\uB2E4.\n\n\n\n        final int MOD = 1_000_000_007;\n        \n        int n = binary.length();\n\n        // for(int i = 0; i < arr.length; i++) System.out.print(arr[i]+ " ");System.out.println();\n\n        long dp[][] = new long[n][2];\n\n        if( binary.charAt(0) == \'0\' )  dp[0][0] = 1;\n        else dp[0][1] = 1;\n\n        long cnt1 = dp[0][1];\n        long cnt0 = dp[0][0];\n\n        for(int i = 1; i < n; i++) {\n            if ( binary.charAt(i) == \'0\' ) cnt0++;\n\n            if ( cnt1 == 0 ) {\n                if ( binary.charAt(i) == \'1\' ) {\n                    dp[i][1] = 1;\n                    cnt1++;\n                }\n            } else{\n                if ( binary.charAt(i) == \'0\' ){\n                    dp[i][0] += dp[i-1][0]+ dp[i-1][1];\n                    dp[i][1] += dp[i-1][1];\n                } else{\n                    dp[i][1] += dp[i-1][0]+ dp[i-1][1]+1;\n                    dp[i][0] += dp[i-1][0];\n                }\n                \n                dp[i][0] %= MOD;\n                dp[i][1] %= MOD;\n            }\n        }\n\n        // for(int i = 0; i <dp.length; i++) {\n        //     System.out.print( "["+ dp[i][0] +  " " + dp[i][1]+ "] ");\n        // } System.out.println();\n        \n        long result = dp[n-1][0] + dp[n-1][1];\n        result %= MOD;\n        if ( cnt0 > 0 && binary.length() > 1)  {\n            result++;\n            result %= MOD;\n        }\n\n        return (int)result;\n    }\n}\n```
['Dynamic Programming', 'Java']