状态压缩动态规划 dp 使用总结

状态压缩

状态压缩就是用进制数（可以是二进制，三进制等等）表示状态，然后进行动态规划 dp。

应用示例

两个数组最大值

对于 students 和 mentors 两个二维数组，两两匹配，计算最大值。

public int maxCompatibilitySum(int[][] students, int[][] mentors) {
    int n = students.length, range = 1 << n;
    int[] dp = new int[range];
    Arrays.fill(dp, Integer.MIN_VALUE);
    dp[0] = 0;
    for (int i = 0; i < range; i++) {
        for (int j = 0; j < n; j++) {
            if (((i >> j) & 1) == 1)//i的第j位为1
                dp[i] = Math.max(dp[i], dp[i ^ (1 << j)] + getVal(students[Integer.bitCount(i) - 1],mentors[j]));
        }
    }
    return dp[range - 1];
}