企业官网建设流程全解析

邯郸企业网站制作,运动品牌网页设计,数码科技网站,哪里有网站建设流程题目与直观理解 题目描述#xff1a;一排房子#xff0c;每间房有一定金额 nums[i]#xff0c;如果同一晚抢了两间相邻的房子就会触发警报#xff0c;问在不触发警报的前提下#xff0c;最多能抢到多少钱。leetcode 直观来说#xff1a;你在一条街上走,每到一间房子一排房子每间房有一定金额nums[i]如果同一晚抢了两间相邻的房子就会触发警报问在不触发警报的前提下最多能抢到多少钱。leetcode直观来说你在一条街上走,每到一间房子都要在两件事里做选择抢但要保证上一间没有抢不抢那就把机会留给后面这个走一条线、每一步只看前面几步的结构非常适合用一维动态规划来建模。leetcode状态设计为什么不是抢了几家而是前缀最优一开始很自然会有这样的想法定义dp[i]为已经抢了 i 家后抢到的钱数然后不断从后面选下一家类似记录 choice 的贪心路径。这个定义有两个核心问题1. 信息不够dp[i]只知道抢了 i 家不知道最后一间是第几号房。但题目的约束是不能抢相邻房要判断是否相邻就必须知道最后一间抢的是哪一间。2. 转移不安全如果写成dp[i] dp[i-1] nums[pos]就隐含假设选第 i 个被抢的房子时不会和之前最后一间相邻。但没有状态信息约束这一点很容易让相邻两间都被选进去违反题意。更自然、也更标准的定义是dp[k]表示只考虑下标从 0 到 k 的这些房子一个前缀在不触发警报的前提下最多能抢到多少钱。leetcode好处状态是前缀最优符合到第 k 间为止的线性结构对第 k 间房只要看抢和不抢两种情况就能写出明确的转移转移方程为什么只看 k-1 和 k-2当考虑第 k 间房下标 k时有两种选择1. 不抢第 k 间那么第 k 间完全忽略答案就是前 k-1 间房的最优dp[k-1]2. 抢第 k 间相邻约束k-1 不能抢于是能加在第 k 间上的是前 k-2 间的最优dp[k-2] nums[k]所以有经典转移d p [ k ] max ⁡ ( d p [ k − 1 ] , d p [ k − 2 ] n u m s [ k ] ) dp[k] \max(dp[k-1], \; dp[k-2] nums[k])dp[k]max(dp[k−1],dp[k−2]nums[k])这时常见疑问来了“为什么不看 k-3、k-4难道不能跳两家、三家抢吗”关键点在于dp[k-2]本身就是前 k-2 间的全局最优。在求dp[0..k-2]的过程中已经自动考虑了中间跳过 1 家、2 家、3 家… 的所有可能方案。当你用dp[k-2]时里面可能对应的是一种跳了很多家的组合而不是只隔一间的简单模式。因此跳几家这件事被折叠进了前缀最优的值里不需要在转移里显式写出 k-3、k-4。对第 k 间只要保证不和最近的 k-1 相邻所以回看 k-2 就足够。k 的范围、为啥要扫完整个数组1. k 的含义与范围在 0-based 写法里通常定义dp[k]考虑[0..k]这些房子共 k1 间能抢到的最大金额这时 k 的范围就是0..numsSize-1答案是dp[numsSize-1]。leetcode如果用 1-based 数学定义如P(k)表示前 k 间的最优那就是k in[1..numsSize]答案是P(numsSize)两者只是下标风格不同本质完全一样。2. “可以中途停止抢” vs “不能中途停止计算”一个容易混淆的点“如果最优方案只抢到中间某一间后就不抢了是不是计算到那间就可以停”从抢劫行为角度最优方案确实可能是只抢前面几间后面都不抢。从DP 计算角度仍然必须把所有房子都考虑一遍让后面都不抢这个决策以dp[k]一直沿用前面的最大值的形式表达出来。比如nums [2, 1, 1, 10]leetcode如果你只算前两个房子可能认为答案是 2真正答案是抢第 0 和第 3 间得到 12只有把 k 一直算到 3dp[3]才能把抢第 3 间这个选择考虑进去所以可以中途停止抢但不能中途停止算。“中途停止抢会自动体现在对后面的每个 k都选择不抢”使dp[k] dp[k-1]。自顶向下递归 记忆化与自底向上是同一件事除了迭代的自底向上你已经写出了一版自顶向下的递归 记忆化代码形式大致是intdp(int*nums,intnumsSize,intpos,int*memo){intmoney;if(pos-1)return0;if(pos0)returnnums[0];if(memo[pos]!-1)returnmemo[pos];moneyMAX(dp(nums,numsSize,pos-1,memo),dp(nums,numsSize,pos-2,memo)nums[pos]);memo[pos]money;returnmoney;}introb(int*nums,intnumsSize){int*memo,money;if(numsSize0)return0;memo(int*)malloc(numsSize*sizeof(int));memset(memo,-1,numsSize*sizeof(int));moneydp(nums,numsSize,numsSize-1,memo);free(memo);returnmoney;}这段代码本质上就是定义f(pos) dp(nums, numsSize, pos, memo)表示考虑[0..pos]这些房子能拿到的最大金额递归关系f(pos) max(f(pos-1), f(pos-2) nums[pos])通过pos -1和pos 0两个 base case把最多向前看两步的转移撑起来。leetcode为什么需要两个边界pos -1 和 pos 0原因在于转移用了f(pos-1)和f(pos-2)计算f(0)时如果统一递归调用会访问到f(-1)如果不用 -1通常就需要在pos 0和pos 1处直接返回结果、避免继续递归因此两种常见写法分别是① 使用 -1 这个虚拟下标f(-1) 0f(0) nums[0]通用递归f(pos) max(f(pos-1), f(pos-2) nums[pos])② 不用 -1下标都非负特判pos 0或pos 1pos 0时返回nums[0]pos 1时返回max(nums[0], nums[1])只在pos 2时使用通用递归式两种写法本质完全一样只是边界处理方式不同。自顶向下 vs 自底向上同一问题的两种姿势自顶向下递归 记忆化从大问题f(n-1)出发递归拆成更小的f(n-2)、f(n-3)……用memo数组避免指数级重复计算时间复杂度变为 O(n)自底向上迭代从最小的问题开始dp[0]、dp[1]循环 k 从 2 到 n-1用dp[k-1]和dp[k-2]推出dp[k]还能进一步优化成只用两个变量prev1相当于dp[k-1]和prev2相当于dp[k-2]做到 O(1) 空间总结无论是哪种方式核心都围绕三个点状态定义前缀最优而不是抢了几家转移关系max(不抢当前, 抢当前 不相邻的前缀)边界条件因为转移向前看两步所以需要两个踏脚点-1 0 或 0 1掌握这道题之后你会发现一维 DP 的典型模式其实就这几个要素找到合适的前缀 / 子问题划分写出当前只依赖前面几步的转移想清楚最小子问题的值并为它们设好边界。相关链接LeetCode 题目链接我的提交记录