企业官网建设流程全解析

成都网站开发公司,wordpress空间服务器,站酷网官网,企业网站建设不足目录 目录 前言 动态规划 一、416分割等和子集 1、题目描述 示例 提示 2、简单理解#xff1f; 3、暴力法 3.1、能不能用图示意#xff1f; 3.2、初始化条件#xff1f; 3.3、边界条件#xff1f; 3.4、代码逻辑#xff1f; 3.5、之前见过但没注意到的…目录目录前言动态规划一、416分割等和子集1、题目描述示例提示2、简单理解3、暴力法3.1、能不能用图示意3.2、初始化条件3.3、边界条件3.4、代码逻辑3.5、之前见过但没注意到的3.6、疑惑点/新知识 3.7、python 代码4、优化法4.1、能不能用图示意4.2、初始化条件4.3、边界条件4.4、代码逻辑4.5、之前见过但没注意到的4.6、疑惑点/新知识 4.7、python 代码前言碎碎念不要问猜到了不要说。本系列《绝境求生》记录转码算法筑基过程以代码随想录为纲学习leetcode_hot_100练手在此记录思考过程方便过后复现。内容比较粗糙仅便于笔者厘清思路复盘总结。刷过的还得再刷3遍 不然白干提示以下是本篇文章正文内容动态规划将复杂的问题拆解成若干个重叠子问题通过求解子问题的最优解逐步推导出原问题的解。可以通过 记忆化 处理避免重复计算子问题来提升效率状态转移方程说白了就是找规律高级一点说法 就是给混沌以秩序。 369 12 dpn dpn - 1 3 。实战把原问题转化为dp问题状态定义一、416分割等和子集1、题目描述给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。关键规则每个元素必须恰好属于其中一个子集不能不选也不能重复选子集不要求连续只需元素和相等。示例示例 1输入nums [1,5,11,5]→ 输出True解释数组和为1511522可分割为[1,5,5]和 11和[11]和 11满足条件。示例 2输入nums [1,2,3,5]→ 输出False解释数组和为123511是奇数无法分割为两个和相等的子集即使和为偶数也需验证是否能凑出目标和。提示1 nums.length 2001 nums[i] 1002、简单理解两个子集的元素和相等为数组总和的一半问题转化为targetsum(nums)//2 看能否从nums中选出若干元素使得和为target。每个元素恰好属于其中一个子集不能不选也不能重复选子集不要求连续。不适合用双指针因为元素和没有单调的规律3、暴力法暴力法一般都会超时这题暴力法用递归难想的一批是默写出来的根本想不到3.1、能不能用图示意以 nums [1,5,11,5]target11 为例 枚举选/不选的状态 递归树dfs(index, remain)index为当前遍历索引remain为剩余目标和 dfs(0,11) → 选1remain10/ 不选1remain11 ├─ dfs(1,10) → 选5remain5/ 不选5remain10 │ ├─ dfs(2,5) → 选11remain-6无效/ 不选11remain5 │ │ └─ dfs(3,5) → 选5remain0返回True/ 不选5remain5返回False │ └─ ...不选5的分支最终返回False └─ ...不选1的分支也能找到True 最终返回True3.2、初始化条件记忆缓存字典 key(index, remain)valuetrue/false状态3.3、边界条件判断数组和是否为奇数是返回False如果某个单一元素直接大于数组和的一半直接返回False3.4、代码逻辑问题转化为targetsum(nums)//2 看能否从nums中选出若干元素使得和为target选当前元素剩余目标-当前元素递归下一个不选剩余目标和不变递归下一个终止条件。当剩余目标和为0。返回true如果遍历完所有元素没凑出和为0 返回false3.5、之前见过但没注意到的选和不选这两个状态怎么用代码写出来 就像打家劫舍一样偷喝不偷3.6、疑惑点/新知识 递归函数dfs就想到终止条件3.7、python 代码from typing import List class Solution: def canPartition(self, nums: List[int]) - int: total sum(nums) # 前置判断1总和为奇数直接返回False if total % 2 ! 0: return False target total // 2 # 前置判断2存在元素大于target直接返回False if max(nums) target: return False # 记忆化缓存key(index, remain)value该状态的结果True/False memo {} # 定义递归函数遍历到index位置剩余目标和为remain返回能否凑出 def dfs(index, remain): # 终止条件1剩余目标和为0凑出返回True if remain 0: return True # 终止条件2遍历完所有元素 或 剩余目标和0未凑出返回False if index len(nums) or remain 0: return False # 查记忆化缓存已有结果直接返回 if (index, remain) in memo: return memo[(index, remain)] # 递归分支1选当前元素剩余目标和减少nums[index] choose dfs(index 1, remain - nums[index]) # 递归分支2不选当前元素剩余目标和不变 not_choose dfs(index 1, remain) # 两种分支有一个为True当前状态就为True res choose or not_choose # 存入缓存供后续复用 memo[(index, remain)] res return res # 从索引0、剩余目标和target开始递归 return dfs(0, target)4、优化法4.1、能不能用图示意以 nums [1,5,11,5]target11 为例 # 初始化dp数组长度12索引0~11 dp [True, False, False, False, False, False, False, False, False, False, False, False] # 遍历第一个元素num1 逆序遍历j11→1 j1: dp[1] dp[1] or dp[1-1] False or True → True dp变为[T, T, F, F, F, F, F, F, F, F, F, F] # 遍历第二个元素num5 逆序遍历j11→5 j5: dp[5] F or dp[0] → T j6: dp[6] F or dp[1] → T dp变为[T, T, F, F, F, T, T, F, F, F, F, F] # 遍历第三个元素num11 逆序遍历j11→11 j11: dp[11] F or dp[0] → T dp变为[T, T, F, F, F, T, T, F, F, F, F, T]已找到True后续可提前终止 # 遍历第四个元素num5无需遍历结果已确定 最终dp[11] True4.2、初始化条件dp[0] 。空子集的时候必满足4.3、边界条件奇数情况还有某个元素已经大于target的情况4.4、代码逻辑dp[j ] j 代表的是nums中的元素从数组里挑元素dp[ j ]表示能否凑出 j 的子集为什么有时候理解不了 dp数组是从dp[0]推导出来的先看dp[1],dp[2] ,dp[ 3 ]j in range(target, num-1,-1) 逆序遍历速度更快,我们的目的是更新dp数组的状态所以怎么方便推出dp[1]dp[2] .......且不重复 就可以用逆序。状态转移dp[j] dp[j] or dp[j - num]dp[j]不选当前 num保持原有状态dp[j - num]选当前 num若 j-num 能凑出则 j 也能凑出。外层循环for num in nums遍历每个元素每个元素只能处理一次0-1 背包特性内层循环range(target, num-1, -1)逆序遍历是关键正序遍历会导致同一元素被多次选中比如 num1j1 更新为 True 后j2 会用 j1 的结果相当于选了两次 1遍历下限是numj num 时j-num 为负看状态转移方程有dp[j-num]无意义无需遍历。4.5、之前见过但没注意到的1、首先要清楚状态定义即状态方程的索引还有值对应啥不然会乱2、dp方程你就想前一个是啥 依赖dp[i-1]还是dp[i-2]还是都依赖还是运算法的依赖,然后想初始化2、把示意图画出来4.6、疑惑点/新知识 分割等和子集即为0-1背包问题就是把分割数组转化为凑目标和背包问题。需要区分0-1背包元素选一次还有无限背包元素取多次的遍历顺序差异牢记 当前状态是基于之前的状态做决策得到的结果4.7、python 代码class Solution: def canPartition(self, nums: List[int]) - bool: total sum(nums) # 前置判断1总和为奇数无法分割 if total % 2 ! 0: return False target total // 2 # 前置判断2存在元素大于目标和无法分割 if max(nums) target: return False # 步骤1初始化dp数组 # dp[j]表示能否凑出和为j的子集长度target1索引0~target # 边界条件dp[0] True和为0的空集存在其余初始为False dp [False] * (target 1) dp[0] True # 步骤2遍历每个元素0-1背包每个元素只能选一次 for num in nums: # 步骤3逆序遍历j从target到num避免重复选同一元素 # 若正序遍历会导致同一元素被多次选中比如num1j1更新后j2会复用j1的结果相当于选了两次1 for j in range(target, num - 1, -1): # 状态转移不选numdp[j] 或 选numdp[j-num] dp[j] dp[j] or dp[j - num] # 提前终止若已找到能凑出target的情况直接返回True if dp[target]: return True # 步骤4返回最终结果 return dp[target]顶级命格的强大之处在于**“非线性的爆发力”**