【DP】898. Bitwise ORs of Subarray

题目描述：

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.

Example 2:

Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.

Note:

1 <= A.length <= 50000
0 <= A[i] <= 10^9

解题思路：

这道题很好理解，但是时间复杂度要求很高，就连普通DP都会超时，容我慢慢道来。

1、直接暴力（TLE）：

• 尝试所有可能的子数组 n^2；
• 对每个子数组计算 Or 操作。

这样，时间复杂度 O(n^3)，空间复杂度 O(1)，肯定不行，想都不用想先pass。

2、普通DP（我使用的方法，但是很可惜还是 TLE 了）：

• 用 dp[i][j] 记录子串 i~j 之间的 Or 操作结果，即 dp[i][j] = A[i] | A[i+1] | ... | A[j]，其中 i >= j；
• 容易找到转移方程 dp[i][j] = dp[i][j-1] + A[j]
• 结果为 ans = len(set(dp))

这样，时间复杂度 O(n^2)，空间复杂度 O(n^2)，还是超时了......

3、高级DP（AC）：

• dp[i] 表示以 A[i] 结尾的所有子数组的 Or 结果，其实是个 set。
• 转移方程式：dp[i] = [(b | A[i]) for b in dp[i-1]] + A[i]，即以 A[i] 结尾的所有子数组 Or 结果等于以 A[i-1] 结尾的所有子数组 Or 结果，和当前的 A[i] 进行 Or 操作，再加上 A[i] 这个结果。注意： len(dp) <= 32，后面会给出证明。
• ans = len(set(dp))

以 A = [1,2,4] 为例，每个位置 A[0]、A[1]、A[2] 的结果分别为 {} | {1} = {1}，{3} | {2} = {2, 3}，{6, 7} | {4} = {4, 6, 7}，因此结果为 {1, 2, 3, 4, 6, 7}。

这时，时间复杂度 O(32*n)，空间复杂度 O(32*n)，接受。

证明：为什么方法 3 中的 len(dp) <= 32 ?

dp[i] = { A[i], A[i]|A[i-1], A[i]|A[i-1]|A[i-2], … , A[i]|A[i-1]|…|A[0] }，这个序列单调递增，通过把 A[i] 中的 0 变成 1。A[i] 最多有 32 个 0，所以这个集合的大小 <= 32。

举例：最坏情况 A = [8, 4, 2, 1, 0]，都是 2^k。
A[5] = 0，dp[5] = { 0, 0|1, 0|1|2, 0|1|2|4, 0|1|2|4|8 } = { 0, 1, 3, 7, 15 }.

Python3 实现：

方法2（TLE）：

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        lens = len(A)
        dp = [[0] * lens for _ in range(lens)]
        res = set()
        for i in range(lens):
            dp[i][i] = A[i]
            res.add(dp[i][i])
            for j in range(i+1, lens):
                dp[i][j] = dp[i][j-1] | A[j]
                res.add(dp[i][j])
        return len(res)

方法3（AC）：

class Solution(object):
    def subarrayBitwiseORs(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        res = set()
        cur = set()  # 保存上一次的结果
        for a in A:
            cur = {n | a for n in cur} | {a}   # n|a为或操作，{}|{}为两个集合的并
            res |= cur  # 更新结果，集合的并
        return len(res)