算法
(动态规划) $O(n)$
本题本质上就是求圆环最大独立集
先考虑序列独立集:$\{a_1, a_2, \cdots, a_n \}$
记 dp[i][0/1]
表示前 $i$ 个数中,要求最后一个数不选/选的最大独立集的和
转移方程:
$ \begin{aligned} &dp[i][0] = \max(dp[i-1][0], dp[i-1][1])\\\ &dp[i][1] = a[i] + dp[i-1][0] \end{aligned} $
对于圆环而言,可以先破环为链:将数组复制一遍放到末尾。
然后枚举一下起点,像上面那样做一遍序列最大独立集。复杂度:$O(n^2)$
但注意到破环为链的适用场合:环或者不环和很多数都有关系的时候。但这里环或者不环只跟 $a_1$ 和 $a_n$ 有关系,所以我们单独处理一下 $a_1$ 和 $a_n$ 即可
- 要求 $a_1$ 可以选
初始化:$dp[1][0] = 0$,$dp[1][1] = a_1$
答案:$dp[n][0]$
- 要求 $a_1$ 不可以选
初始化:$dp[1][0] = 0$
答案:$\max(dp[n][0], dp[n][1])$
所以,最后的答案为 $\max(dp[n][0], \max(dp[n][0], dp[n][1]))$
C++ 代码
class Solution {
public:
int rob(vector<int>& a) {
int n = a.size();
if (n == 1) return a[0];
vector dp(n, vector<int>(2));
dp[0][0] = 0; // 不选开头,结尾可以选或不选
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0] + a[i];
}
int res = max(dp[n-1][0], dp[n-1][1]);
dp[0][1] = a[0]; // 选开头,结尾只能不选
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
dp[i][1] = dp[i-1][0] + a[i];
}
res = max(res, dp[n-1][0]);
return res;
}
};
终于看到一个用状态机那种模板写这一类题的了,点个赞