198.打家劫舍
要求：
给定一个nums，要求取得最大值，但是不可以选择两个相邻的数
dp定义：
dp[n]，取到第N个数字的时候，最大值
递推公式：
取：nums[i] + dp[j-2]
不取： nums[i-1];
代码：
1 // 在两个数字不相邻的情况下，得到的最大金额 2 // 思路： 3 // dp[n] 第N个数字时的最大金额数 4 // 难点： 5 // 1,如何做到全局最大 4 7 9 1 6 // 2,中间还可能不相隔 2 1 1 2 7 // 8 // dp[j] 取，不取 9 // dp[j-1] , value[i]+dp[j-2];. 10 // 11 // 初始化？因为第0个也不一定被拿到 12 // 13 // 根据定义：dp[0] = nums[0] dp[1] = max 14 // 15 // 如何巧妙的可以用到之前的数值，同时不固定必须的选择顺序， 16 // dp = max(dp[j-1], nums[1]+dp[j-2]) 17 // 18 int rob(vector<int>& nums) { 19 if (nums.size() == 1)return nums[0]; 20 21 vector<int>dp(nums.size(), 0); 22 dp[0] = nums[0]; 23 dp[1] = max(nums[0], nums[1]); 24 25 for (int i = 2; i < nums.size(); i++) 26 { 27 dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]); 28 } 29 30 return dp[nums.size() - 1]; 31 }