1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public long numberOfWays(String s) {
        long picksEndWith0 = 0, picksEndWith1 = 0, ans = 0;
        int zeroCount = 0, oneCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                ans += picksEndWith1;
                picksEndWith0 = picksEndWith0 + oneCount;
                zeroCount += 1;
            } else {
                ans += picksEndWith0;
                picksEndWith1 = picksEndWith1 + zeroCount;
                oneCount += 1;
            }
        }
        return ans;
    }
}

这道题本来想着用recursion + memo做, 但发现有三个状态: 到了可以从哪个位置之后进行选择, 此时不能选择什么以及目前选了多少个. 于是我们就在想dp. 看这道题能不能转化为subproblem的形式. 找到一种就是s中的每一个char假设作为三个building中的最后一个, 有多少个? 这样把每个char都作为building最后一个的结果加在一起就是答案. 那么我们怎么知道呢? 比如我想知道i这个位置作为building最后一个的时候, 有多少种凑法. 那么分两种情况: 首先是i这个位置是0. 那么我需要知道i之前任意选两个且结尾是1的选法有多少种, 这些选法再把这个i凑上去就能够构成valid的三个building并且也是以i结尾的. 类似地, 如果i这个位置是1, 我就要知道i之前选两个且以0结尾的选法有多少种. 然后我们同样告诉我们后一个位置, 从i以及之前的位置选两个以0结尾的有多少个, 以及以1结尾的有多少个, 这样我们后一个位置作为building中最后一个时才能知道答案. 那么我们如何根据之前的答案求当前的状态呢?

如果i是0, 那么我们想知道[0, i]取两个且以1结尾的选法其实就是[0, i - 1]以1结尾的选法. 对于选两个结尾是0的话, 答案就是[0, i - 1]取两个0结尾的选法 + [0, i - 1]1的个数, 这样和i这个0配对就是i为结尾的选法.

如果i是1也是类似地. 想知道[0, i]选两个以0结尾, 那其实就是[0, i - 1]选两个0结尾的选法. 想知道[0, i]选两个以1结尾, 那就是[0, i - 1]以0结尾的选法 + [0, i - 1]0个个数然后和i这个1配对就是i为结尾的选法.

dp[i][0]表示从前i个元素选两个以0结尾的选法
dp[i][1]表示从前i个元素选两个以1结尾的选法
那么当i是1的时候: dp[i][0] = dp[i - 1][0]; dp[i][1] = dp[i - 1][1] + 从0到i - 1, 0的个数.
那么当i是0的时候: dp[i][1] = dp[i - 1][1]; dp[i][0] = dp[i - 1][0] + 从0到i - 1, 1的个数.

其实可以初始化为长度为s.length()的dp数组, 但是我们只用到上一个状态, 因此四个变量即可:
从0到当前位置(exclusive)0的个数, 1的个数, 选两个0结尾的选法以及选两个1结尾的选法.

这样就可以了.

时间复杂度: O(n)
空间复杂度: O(1)