小偷最优偷窃策略：动态规划解法

LeetCode198你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你不触动警报装置的情况下一夜之内能够偷窃到的最高金额。示例 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 。Python解法动态规划class Solution: def rob(self, nums: List[int]) - int: if not nums: return 0 elif len(nums) 1: return nums[0] n len(nums) dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i - 2] nums[i], dp[i - 1]) return dp[n - 1]Java解法class Solution{ public int rob(int[] nums){ if(nums null){ return 0; }else if(nums.length 1){ return nums[0]; } n nums.length; int[] dp new int[n]; dp[0] nums[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]; } }C解法class Solution{ public: int rob(vectorint nums){ if(nums.empty()){ return 0; }else if(nums.size() 1){ return nums[0]; } int n nums.size(); vectorint dp vectorint(n, 0); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for(int i 2; i n; i){ dp[i] max(dp[i - 2] nums[i], dp[i - 1]); } return dp[n - 1]; } };动态规划解析一、动态规划本质一句话拆分重复子问题缓存子问题答案避免重复计算自底向上 / 自顶向下推全局最优解。暴力递归会大量重复算相同子问题DP 把算过的结果存起来空间换时间。二、DP 三大核心特征判断能不能用 DP满足下面全部 3 点才适合动态规划1. 最优子结构大问题的最优解 若干更小子问题的最优解组合而成。 例爬楼梯 n 阶最优走法由 n-1、n-2 阶最优解推出。2. 重叠子问题递归分解后会反复计算一模一样的小子问题。 暴力递归指数级时间DP 缓存后降到多项式。3. 无后效性一旦算出某个子问题的结果后续推导不会再改变它当前状态只依赖前面已算完的状态不依赖未来未发生的状态。