https://leetcode.com/problems/house-robber/
题意：
一维数组，相加不相邻的数组，返回最大的结果。
思路：
一开始思路就是DP，用一维数组保存dp[i]保存如果偷第i间，此时可偷到多少。DP的方向不太好，所以效率很低。
Runtime: 4 ms, faster than 17.53%
class Solution { public:int rob(vector<int> &nums){int res = 0;int len = nums.size();if (len <= 0)return res;int dp[len];for (int i = 0; i < len; i++){dp[i] = nums[i];res = max(res, dp[i]);}if (len > 2){dp[2] += dp[0];res = max(res, dp[2]);}for (int j = 3; j < len; j++){dp[j] += max(dp[j - 2], dp[j - 3]);res = max(res, dp[j]);}return res;} };
后面DP思路改成：dp[i]记录在偷到第i位时，最大可偷多少钱。
可偷最多的钱要么是偷这次的，要么是不偷这一次的。
转移方程为： dp[i]=max(dp[i-2]+nums[i],dp[i-1])
Runtime: 0 ms, faster than 100.00%
class Solution { public:int rob(vector<int> &nums){int res = 0;int len = nums.size();if (len <= 0)return res;if (len == 1)return nums[0];if (len == 2)return (nums[0] > nums[1] ? nums[0] : nums[1]);int dp[len];dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < len; i++){dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[len - 1];} };