动态规划-打家劫舍、股票问题
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
首尾相邻，故考虑首尾元素分三种情况：
- 考虑不包含首尾
- 考虑包含首元素，不包含尾
- 考虑包含尾，不包含首
第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];}
}