# 2172. Maximum AND Sum of Array
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/maximum-and-sum-of-array/description/
## 思路
显然是一道要用状态压缩的dp题
一开始的想法是状态压缩nums 但是nums可能比numSlots大一倍 所以压缩numSlots更好
我们用3进制的state表示numSlots 如果第i位是0/1/2 说明第(i+1)个slot有0/1/2个数
于是dp[i][state]表达的是：用完第i个数字、配对了state所表示的slots时，所得的最大价值。所以核心代码大致会是：

 for (int i=0; i<nums.size(); i++)
    for (int nextState=0; nextState<pow(3, numSlots); nextState++)
      for (auto pickedSlot: prevState)
        dp[i][nextState] = dp[i-1][prevState] + (nums[i] & pickedSlot);

对于每一个number 我们遍历所有的nextState(也就是加上这个num之后的state) 然后我们要找到前一个state 然后算出前一个state+把当下number放到某一个slot里面使得state变成nextState所带来的收益
那么怎么找前一个state呢？找出nextState里面所有非空的slot 也就是pickedSlot 给这个slot里面的element数-1 就是前一个state了
### 优化
由于state里面已经涵盖了现在用了几个数字了 所以不需要第一层回圈

**注意: &的优先级比+低 line13一定要给(j+1)&num加括号**
## Code
### 思路一

class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int n = nums.length;
        int[][] dp = new int[n+1][(int)Math.pow(3, numSlots)];
        // Arrays.fill(dp[0], Integer.MIN_VALUE);
        // dp[0][0] = 0;
        int ans = 0;
        for(int i=1; i<=n; i++){
            int num = nums[i-1];
            for(int state=1; state<Math.pow(3, numSlots); state++){
                for(int j=0; j<numSlots; j++){
                    if(filled(state, j)){
                        dp[i][state] = Math.max(dp[i][state], dp[i-1][state-(int)(Math.pow(3, j))]+((j+1)&num));
                    }
                }
                if(i==n) ans = Math.max(ans, dp[n][state]);
            }
        }
        return ans;
    }
    private boolean filled(int state, int k){
        for(int i=0; i<k; i++){
            state/=3;
        }
        return state%3>=1;
    }
}

### 优化

class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        int n = nums.length;
        int[][] dp = new int[n+1][(int)Math.pow(3, numSlots)];
        int ans = 0;
        for(int state=1; state<Math.pow(3, numSlots); state++){
            int temp = state;
            int count = 0;
            while(temp>0){
                count += temp%3;
                temp/=3;
            }
            int i = count;
            if(i>n) continue;  
            for(int j=0; j<numSlots; j++){
                if(filled(state, j)){
                    dp[i][state] = Math.max(dp[i][state], dp[i-1][state-(int)(Math.pow(3, j))]+((j+1)&nums[i-1]));
                }
            }
            if(i==n) ans = Math.max(ans, dp[n][state]);
        }
        return ans;
    }
    private boolean filled(int state, int k){
        for(int i=0; i<k; i++){
            state/=3;
        }
        return state%3>=1;
    }
}