Leetcode week 4: maximum sum of arrays (shape pressing DP bit operation)

Ideas ：
1. Use bit operation to compress the state of basket vacancy
2. Use dp, To represent in a given state , front i Maximum and sum of

src：

class Solution:
    def maximumANDSum(self, nums: List[int], numSlots: int) -> int:

        # f(i, mask) Show consideration nums In front of i It's an integer , Basket availability status is mask
        @lru_cache(None)
        def f(i, mask):
            if i < 0:
                return 0
            t, w, res = mask, 1, 0
            #  Traverse the basket 
            for k in range(1, numSlots + 1):
                #  Ruodi k Baskets are still available 
                if t % 3:
                    #  Choose him , And the previous results 
                    res = max(res, f(i - 1, mask - w) + (k & nums[i]))
                #  Consider the next basket 
                t, w = t // 3, w * 3
            return res
        
        return f(len(nums) - 1, 3 ** numSlots - 1)

summary ：
[email protected]_cache Memory search
2. use n Binary to compress the state （n States ）
3. Traverse all possible , Take out the biggest