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 }
标签：打家劫舍,198,nums,max,随想录,第三十六,dp,size From： https://www.cnblogs.com/smartisn/p/17576375.html