21天掌握动态规划
第二天 线性动态规划
2.1 53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [0] 输出：0
示例 4：
输入：nums = [-1] 输出：-1
示例 5：
输入：nums = [-100000] 输出：-100000
提示：
class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n + 1]; dp[0] = nums[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); } int maxn = nums[0]; for (int i = 0; i < n; i++) { maxn = Math.max(dp[i],maxn); } return maxn; } }
空间复杂度进行优化
class Solution { public int maxSubArray(int[] nums) { int pre = 0, res = nums[0]; int n = nums.length; for (int i = 0; i < n; i++) { pre = Math.max(pre + nums[i],nums[i]); res = Math.max(pre,res); } return res; } }
2.2 198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
由此，可以写出该题目代码，
Java代码如下：
class Solution { public int rob(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; if (n == 1) { return dp[0]; } dp[1] = Math.max(nums[0],nums[1]); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]); } return dp[n - 1]; } }
空间复杂度优化
class Solution { public int rob(int[] nums) { int pre = 0; int cur = 0; for (int i = 0; i < nums.length; i++) { int tmp = Math.max(pre + nums[i],cur); pre = cur; cur = tmp; } return cur; } }
2.3 213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [0] 输出：0
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
这个题与198. 打家劫舍题，唯一的区别在于房子首部和房子尾部是连接起来成一个环。大致思路是一样的
Java代码如下：
class Solution { public int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } return Math.max(myrob(Arrays.copyOfRange(nums,0,nums.length-1)),myrob(Arrays.copyOfRange(nums,1,nums.length))); } public int myrob(int[] nums) { int pre = 0; int cur = 0; for (int i = 0; i < nums.length; i++) { int tmp = Math.max(cur,pre + nums[i]); pre = cur; cur = tmp; } return cur; } }
