推 oin1104: 大師 07/28 21:42
→ PogChampLUL: 大師 07/28 21:49
DP stage i算出只看nums[:i+1]，所有subset對應的element-wise or的value的count
要進入stage i+1，只要把nums[i+1]跟map內所有item or過一次更新map即可
def countMaxOrSubsets(self, nums: List[int]) -> int:
target = 0
for num in nums:
target = target|num
mp = defaultdict(int)
mp[0] = 1
for num in nums:
tmp = defaultdict(int)
for k,v in mp.items():
if k|num < target:
tmp[k|num] += v
else:
tmp[target] += v
for k,v in tmp.items():
mp[k] += v
return mp[target]
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1753709861.A.EFE.html