实现这道题的核心思路是利用状态压缩动态规划。因为 time[i] 最大只有 5，所以可以用一个 5 位的二进制数来表示某个舱室在 5 个时刻的屏障开启情况。问题的难点在于处理相邻舱室的联合屏障，我们可以通过枚举上一个舱室在哪些时刻开启了联合屏障来解决。
以下是详细解析和可直接运行的Java代码。
解题思路
1. 数据表示：用 rain[p] 的二进制低5位表示位置 p 在哪些时刻有陨石。第 t 时刻有陨石，则第 t 位（从0开始）为1。
2. 预处理代价：对于任意一个状态 j（二进制表示哪些时刻有屏障），计算单独开启这些屏障所需的最小能量 single[j]。如果同一个舱室在两个相邻时刻都需要屏障，则第二个时刻只需花 1 点能量维持即可，否则需要花 2 点能量重新开启。
3. 核心DP：dp[i][j] 表示处理到第 i 个舱室，且第 i 个舱室与第 i+1 个舱室在时刻集合 j 开启联合屏障时的最小总能量。
· 当计算 dp[i][j] 时，枚举上一个舱室 i-1 的联合屏障时刻集合 pre。注意 pre 和 j 不能有交集，因为一个时刻一个舱室不能被两个屏障覆盖。
· 状态转移方程：dp[i][j] = min(dp[i-1][pre] + cost)。
· 这个 cost 是第 i 个舱室的总开销，包含三部分：
· 开启联合屏障的花费：union[j]。
· 针对“既没有与左边联合，也没有与右边联合”的时刻，开启单独屏障的花费：需要单独屏障的时刻集合 = (所有时刻补集 ^ j) & rain[i]，其花费为 single[该集合]。
· 注意：第 i 个舱室被左边联合屏障保护的时刻 pre 不需要再付任何费用。
Java实现代码
```java
class Solution {
public int defendSpaceCity(int[] time, int[] position) {
int maxPos = 0, maxTime = 0;
for (int t : time) maxTime = Math.max(maxTime, t);
for (int p : position) maxPos = Math.max(maxPos, p);
int m = 1 << maxTime; // 状态总数，因为time最大为5，所以m最大为32
int[] rain = new int[maxPos + 1];
for (int i = 0; i < time.length; i++) {
// 将时刻映射到二进制的第 (time[i]-1) 位
rain[position[i]] |= 1 << (time[i] - 1);
}
// 1. 预处理单屏障和联合屏障的代价
int[] single = new int[m];
int[] union = new int[m];
for (int i = 1; i < m; i++) {
int lb = i & -i; // 最低位的1
int j = i ^ lb; // 去掉最低位的1
int lb2 = j & -j; // 前一个状态的连续段
// 判断这个新加的1时刻是否与原有最右侧时刻相邻
boolean isAdjacent = (lb == (lb2 >> 1));
// 单独屏障：首次开需要2，维持需要1
single[i] = single[j] + (isAdjacent ? 1 : 2);
// 联合屏障：首次开需要3，维持需要1
union[i] = union[j] + (isAdjacent ? 1 : 3);
}
// 2. DP
int INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[maxPos + 2][m];
for (int i = 0; i <= maxPos + 1; i++) {
Arrays.fill(dp[i], INF);
}
// 初始化第0个舱室，它没有左边的舱室，所以 pre 只能是 0
for (int j = 0; j < m; j++) {
// 第0个舱室不能与左边联合，所以它的花费只有：自己开联合 + 针对剩余时刻开单屏障
int mask = (m - 1) ^ j; // 所有时刻中，没有与右边联合的时刻集合
int needSingle = mask & rain[0];
dp[0][j] = union[j] + single[needSingle];
}
// 遍历从1到maxPos的每个舱室
for (int i = 1; i <= maxPos; i++) {
for (int j = 0; j < m; j++) {
// 枚举上一个舱室 i-1 的联合屏障集合 pre
// pre 必须是 j 的补集的子集，即 (pre & j) == 0
int mask = (m - 1) ^ j;
for (int pre = mask; ; pre = (pre - 1) & mask) {
// 计算当前舱室 i 需要单独屏障的时刻
// 这些时刻是：既没有与左边联合(pre)，也没有与右边联合(j)，并且有陨石
int needSingle = (mask ^ pre) & rain[i];
int cost = dp[i - 1][pre] + union[j] + single[needSingle];
dp[i][j] = Math.min(dp[i][j], cost);
if (pre == 0) break;
}
}
}
// 答案：最后一个舱室之后没有舱室了，所以它不能与右边联合，状态j必须为0
// 但我们的dp定义是第i个舱室与i+1联合，所以需要再处理一个虚拟舱室，强制其j=0
// 或者直接取 dp[maxPos][0]，因为最后一个舱室的右边没有舱室，状态必须为0
// 更严谨的写法是再做一个虚拟舱室的转移
int ans = INF;
for (int pre = 0; pre < m; pre++) {
// 虚拟位置 maxPos + 1，没有陨石，且联合状态 j 必须为 0
int needSingle = ((m - 1) ^ pre) & 0; // 无陨石
ans = Math.min(ans, dp[maxPos][pre] + single[0]);
}
return ans;
}
}
```
