给定整数数组 a,从中选若干元素使任意两个被选元素在原数组中都不相邻,且所选元素总和最大(打家劫舍)。下面 DP 代码横线处应填写( )。
int choose(vector<int>& a) {
if (a.empty()) return 0;
int n = a.size();
if (n == 1) return a[0];
vector<int> dp(n, 0);
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for (int i = 2; i < n; ++i) {
dp[i] = ________________________;
}
return dp[n - 1];
}
- A. dp[i - 1] + a[i]
- B. max(dp[i - 1], dp[i - 2] + a[i])
- C. max(dp[i - 2], a[i])
- D. dp[i - 1] + dp[i - 2]
正确答案：B