Leetcode 198 题
Difficulty:Easy
Tag: Dynamic Programming
题意
题目原址：https://leetcode.com/problems/house-robber/?tab=Description
这道题的本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。
解法
动态规划
设 $rob[i]$ 为表示到 $i$ 位置时不相邻数能形成的最大和. 接下来以$rob[i]$推到出递推公式。
对于如下一个数组$nums = [3, 2, 1 ,4]$.
我们的目标是使rob[i]最大
i = 0，毫无疑问 rob[0] = 3
i = 1, 需要从第一个位置和当前位置选一个最大的出来，由于 3 > 2, rob[1] = 3
i = 2，由于不能是相邻数，所以需要考虑在再前一个位置和当前位置的和
与前一个位置的rob中选一个最大的出来，即max(nums[i] + rob[i - 2], rob[i - 1])
由此可见 rob[0]与rob[1]是初始条件
递推公式
\[rob(i) = \begin{cases} rob[0] = nums[0], & \text{ i = 0} \\ rob[1] = \max(nums[0], nums[1]), & \text{ i = 1 } \\ rob[i] = \max(nums[i] + rob[i - 2], rob[i - 1]), & \text{ $i \gt 1$ } \end{cases}\]实现
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() <= 1) return nums.empty() ? 0 : nums[0];
vector<int> rob = {nums[0], max(nums[0], nums[1])};
int i = 2;
for(; i < nums.size(); i++)
{
rob.push_back(max(nums[i] + rob[i - 2], rob[i - 1]));
}
return rob.back();
}
};