动态规划-打家劫舍、股票问题

198.打家劫舍  - 力扣（LeetCode）

1.dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

2.dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3.初始化：

dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

4.从前往后 

class Solution {public int rob(int[] nums) {int n = nums.length;if(nums == null || n  == 0) return 0;if(n==1) return nums[0];if(n==2) return Math.max(nums[0],nums[1]);int[] dp = new int[n];dp[0] = nums[0]; dp[1] = Math.max(dp[0],dp[1]);for(int i=2; i<n; i++){dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[n-1];}
}

 213. 打家劫舍 II

首尾相邻，故考虑首尾元素分三种情况：

1. 考虑不包含首尾
2. 考虑包含首元素，不包含尾
3. 考虑包含尾，不包含首

第2、3都包含了1，所以只考虑2、3即可，即要首元素或是不要首元素两种情况

class Solution {public int[] dp;public int rob(int[] nums) {int n = nums.length;if(n==0) return 0;if(n==1) return nums[0];if(n==2) return Math.max(nums[0],nums[1]);dp = new int[n];return Math.max(rob(nums, 1,n-1), nums[0]+rob(nums,2,n-2));}public int rob(int[] nums, int l, int r){if(l>r) return 0;if(l==r) return nums[l];dp[l] = nums[l]; dp[l+1] = Math.max(dp[l],nums[l+1]);for(int i=l+2; i<=r; i++){dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[r];}
}