做网站好处小程序原生开发

做网站好处,小程序原生开发,做网站的项目介绍,嵌入式培训一般多少钱目录 方法 1#xff1a;朴素回溯#xff08;暴力递归#xff09; 思路 Java 实现 时空复杂度 问题 方法 2#xff1a;记忆化搜索#xff08;自顶向下 DP#xff09; 思路 Java 实现 时空复杂度 优化点 方法 3#xff1a;自底向上的动态规划#xff08;DP 数组…目录方法 1朴素回溯暴力递归思路Java 实现时空复杂度问题方法 2记忆化搜索自顶向下 DP思路Java 实现时空复杂度优化点方法 3自底向上的动态规划DP 数组思路Java 实现时空复杂度优化点方法 4空间优化的动态规划双变量思路Java 实现时空复杂度优化点优化变迁总结打家劫舍问题的核心是 “相邻房屋不能同时偷”我们从暴力回溯开始逐步优化到空间最优的动态规划下面分步骤解析方法 1朴素回溯暴力递归思路通过递归枚举每个房屋的两种选择偷当前房屋则只能偷前 i-2 个房屋的最大金额 当前金额、不偷当前房屋则偷前 i-1 个房屋的最大金额。状态定义dfs(i)表示 “考虑前 i 个房屋时的最大偷窃金额”。Java 实现class Solution { public int rob(int[] nums) { return dfs(nums, nums.length - 1); } // 递归计算前i个房屋的最大金额 private int dfs(int[] nums, int i) { if (i 0) return 0; // 边界没有房屋时金额为0 // 选择1不偷i取前i-1的最大选择2偷i取前i-2的最大当前金额 return Math.max(dfs(nums, i - 1), dfs(nums, i - 2) nums[i]); } }时空复杂度时间复杂度O(2n)每个房屋分 2 种选择递归树深度为 n总节点数是2n级空间复杂度O(n)递归栈的深度为 n问题存在大量重复计算例如计算dfs(5)需要dfs(4)和dfs(3)计算dfs(4)又需要dfs(3)和dfs(2)dfs(3)会被多次计算效率极低n≥20 时就会超时。方法 2记忆化搜索自顶向下 DP思路用 ** 备忘录数组** 存储已经计算过的dfs(i)结果避免重复计算 —— 每次计算前先检查备忘录若已存在结果则直接返回否则计算后存入备忘录。Java 实现import java.util.Arrays; class Solution { private int[] memo; // 备忘录存储每个i对应的最大金额 public int rob(int[] nums) { int n nums.length; memo new int[n]; Arrays.fill(memo, -1); // 初始化-1表示该位置未计算金额非负不会和有效结果冲突 return dfs(nums, n - 1); } private int dfs(int[] nums, int i) { if (i 0) return 0; if (memo[i] ! -1) return memo[i]; // 已计算直接返回 // 计算并存入备忘录 int res Math.max(dfs(nums, i - 1), dfs(nums, i - 2) nums[i]); memo[i] res; return res; } }时空复杂度时间复杂度O(n)每个 i 只计算 1 次空间复杂度O(n)备忘录数组 递归栈优化点解决了 “重复计算” 的问题将时间复杂度从指数级降到线性但仍依赖递归栈。方法 3自底向上的动态规划DP 数组思路把 “自顶向下的递归” 改成 “自底向上的迭代”用DP 数组存储每个位置的最大金额彻底避免递归栈。状态定义dp[i]表示 “前 i 个房屋的最大偷窃金额”。状态转移不偷第 i 个房屋dp[i] dp[i-1]偷第 i 个房屋dp[i] dp[i-2] nums[i-1]nums 索引比 dp 小 1因为 dp [0] 对应 “0 个房屋”Java 实现class Solution { public int rob(int[] nums) { int n nums.length; if (n 0) return 0; // dp[i]前i个房屋的最大金额i从0到n int[] dp new int[n 1]; dp[0] 0; // 0个房屋金额0 dp[1] nums[0]; // 1个房屋金额为nums[0] // 从第2个房屋开始迭代 for (int i 2; i n; i) { dp[i] Math.max(dp[i - 1], dp[i - 2] nums[i - 1]); } return dp[n]; } }时空复杂度时间复杂度O(n)仅需遍历 1 次空间复杂度O(n)DP 数组占用 n1 空间优化点用迭代替代递归避免了递归栈溢出的风险但空间仍依赖数组。方法 4空间优化的动态规划双变量思路观察状态转移dp[i]只依赖dp[i-1]和dp[i-2]因此不需要整个 DP 数组只需用两个变量分别存储这两个依赖值即可。Java 实现class Solution { public int rob(int[] nums) { int f0 0; // 对应dp[i-2]前i-2个房屋的最大金额 int f1 0; // 对应dp[i-1]前i-1个房屋的最大金额 for (int x : nums) { int newF Math.max(f1, f0 x); // 计算当前房屋的最大金额 f0 f1; // 更新f0为原来的f1i-1 → i-2 f1 newF; // 更新f1为当前的newFi → i-1 } return f1; } }时空复杂度时间复杂度O(n)遍历 1 次空间复杂度O(1)仅用 2 个变量优化点将空间复杂度从O(n)降到O(1)是该问题的最优空间方案。优化变迁总结朴素回溯O(2^n)时间 ↓ 解决重复计算 记忆化搜索O(n)时间O(n)空间 ↓ 去掉递归栈改为迭代 自底向上DP数组O(n)时间O(n)空间 ↓ 去掉冗余数组用双变量替代 空间优化DPO(n)时间O(1)空间