企业官网建设流程全解析

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(vector<int>& nums){ if(nums.empty()){ return 0; }else if(nums.size() == 1){ return nums[0]; } int n = nums.size(); vector<int> dp = vector<int>(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. 无后效性

一旦算出某个子问题的结果，后续推导不会再改变它；当前状态只依赖前面已算完的状态，不依赖未来未发生的状态。