leetcode1987 不同的好子序列数目

思路：

动态规划，参考了https://leetcode-cn.com/problems/number-of-unique-good-subsequences/solution/bu-tong-de-hao-zi-xu-lie-shu-mu-by-leetc-ej2n/。

实现：

 1 class Solution
 2 {
 3 public:
 4     int numberOfUniqueGoodSubsequences(string binary)
 5     {
 6         int n = binary.length(), mod = 1e9 + 7;
 7         int res = 0, a = 0, b = 0;
 8         for (int i = 1; i <= n; i++)
 9         {
10             int new_a = 0, new_b = 0;
11             if (binary[i - 1] == '1')
12             {
13                 new_a = a;
14                 new_b = (a + b + 1) % mod;
15             }
16             else 
17             {
18                 if (res == 0) res++;
19                 new_a = (a + b) % mod;
20                 new_b = b;
21             }
22             a = new_a; b = new_b;
23         }
24         res = (res + a + b) % mod;
25         return res;
26     }
27 };