企业官网建设流程全解析

网站域名怎么设置,wordpress 翻页函数,电商网站的人员团队建设,wordpress地图定位一、什么是状态压缩动态规划 状态压缩DP是用二进制位或位运算来表示和存储状态的一类DP#xff0c;主要用于解决状态维度高但每个维度状态数少的问题#xff08;通常是布尔值#xff09;。 典型特征#xff1a; 状态中的每一维只有少量可能值#xff08;通常是0/1#…一、什么是状态压缩动态规划状态压缩DP是用二进制位或位运算来表示和存储状态的一类DP主要用于解决状态维度高但每个维度状态数少的问题通常是布尔值。典型特征状态中的每一维只有少量可能值通常是0/1状态空间巨大但可压缩常与排列、选择、覆盖等问题相关二、状态压缩的核心技巧1.二进制位表示法python复制下载# 用整数mask的二进制位表示选择状态 mask 0b10101 # 表示第0、2、4个元素被选中 n 5 for i in range(n): if mask (1 i): # 检查第i位是否为1 print(f元素{i}被选中)2.常见位运算操作python复制下载# 基本操作 S (1 n) - 1 # n位全1 S (1 i) # 判断第i位是否为1 S | (1 i) # 设置第i位为1 S ~(1 i) # 设置第i位为0 S ^ (1 i) # 翻转第i位 S (S - 1) # 清除最低位的1三、经典问题模型1.旅行商问题TSPpython复制下载def tsp(n, dist): # dp[mask][i]: 访问过mask中的城市最后在i城市的最小代价 dp [[float(inf)] * n for _ in range(1 n)] dp[1][0] 0 # 从城市0开始 for mask in range(1 n): for i in range(n): if not (mask (1 i)): continue for j in range(n): if mask (1 j): continue new_mask mask | (1 j) dp[new_mask][j] min(dp[new_mask][j], dp[mask][i] dist[i][j]) # 返回起点并形成环路 return min(dp[(1 n) - 1][i] dist[i][0] for i in range(1, n))2.棋盘覆盖问题python复制下载def domino_cover(n, m): # dp[i][mask]: 处理到第i行当前行状态为mask dp [0] * (1 m) dp[(1 m) - 1] 1 # 初始状态 for i in range(n): new_dp [0] * (1 m) for mask in range(1 m): if dp[mask] 0: continue # 递归填充当前行 def dfs(col, current_mask, next_mask): if col m: new_dp[next_mask] dp[mask] return # 如果当前位置已被覆盖 if mask (1 col): dfs(col 1, current_mask, next_mask) else: # 竖放 if i n - 1: dfs(col 1, current_mask | (1 col), next_mask | (1 col)) # 横放 if col m - 1 and not (mask (1 (col 1))): dfs(col 2, current_mask | (3 col), next_mask) dfs(0, 0, 0) dp new_dp return dp[(1 m) - 1]篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc需要全套面试笔记及答案【点击此处即可/免费获取】​​​四、高级优化技巧1.枚举子集优化python复制下载# 高效枚举mask的所有子集 def enumerate_subsets(mask): subset mask while subset: # 处理子集subset process(subset) subset (subset - 1) mask # 处理空集 process(0) # 复杂度O(3^n) 而非 O(4^n) for mask in range(1 n): subset mask while subset: # subset是mask的子集 complement mask ^ subset # mask除去subset的部分 subset (subset - 1) mask2.滚动数组优化python复制下载# 二维降一维 dp [0] * (1 n) dp[0] 1 for i in range(m): new_dp [0] * (1 n) for mask in range(1 n): if dp[mask]: # 状态转移 for new_mask in next_masks(mask): new_dp[new_mask] dp[mask] dp new_dp3.预处理合法状态python复制下载# 预处理所有合法状态减少无效转移 def preprocess_states(n): valid_states [] for mask in range(1 n): # 检查是否没有相邻的1 if not (mask (mask 1)): valid_states.append(mask) return valid_states # 预处理状态间转移 def preprocess_transitions(valid_states): transitions {} for s1 in valid_states: transitions[s1] [] for s2 in valid_states: if not (s1 s2): # 状态兼容性检查 transitions[s1].append(s2) return transitions4.Meet-in-the-Middlepython复制下载def meet_in_middle(n, target): half n // 2 left_sums {} # 枚举前半部分 for mask in range(1 half): s sum(nums[i] for i in range(half) if mask (1 i)) left_sums[s] left_sums.get(s, 0) 1 # 枚举后半部分 result 0 for mask in range(1 (n - half)): s sum(nums[half i] for i in range(n - half) if mask (1 i)) if target - s in left_sums: result left_sums[target - s] return result篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc需要全套面试笔记及答案【点击此处即可/免费获取】​​​五、实战技巧总结1.空间优化优先级text复制下载位运算压缩 → 滚动数组 → 按块处理 → 状态哈希2.时间优化策略预处理合法状态和转移使用位运算加速状态检查剪枝无效状态使用对称性减少状态数3.常见易错点python复制下载# 错误忘记处理空集 subset mask while True: # 这样会跳过空集 # ... if subset 0: break subset (subset - 1) mask # 正确显式处理空集 subset mask while subset: # ... subset (subset - 1) mask # 处理空集 process(0)六、复杂度分析问题类型状态数常见复杂度优化目标普通状态压缩O(2^n)O(2^n * n)减少n或优化转移带约束压缩O(有效状态)O(状态数²)预处理合法状态多维压缩O(2^(n*m))指数级Meet-in-Middle七、练习题推荐入门LeetCode 78子集、LeetCode 526优美的排列中等LeetCode 464我能赢吗、LeetCode 691贴纸拼词进阶LeetCode 1434每个人戴不同帽子的方案数竞赛级POJ 2411铺砖、UVa 11825黑客攻击八、最佳实践建议先写朴素DP再压缩确保逻辑正确后再优化状态设计要简洁能用1位不用2位善用位运算函数提高代码可读性注意位序方向统一从低位到高位或反之测试边界情况空集、全集、最大规模掌握状态压缩的关键在于多练习、多总结。从经典的TSP和铺砖问题开始逐步扩展到更复杂的问题你会逐渐建立状态设计的直觉。记住好的状态设计能让复杂问题变得简单而差的设计会让简单问题变得复杂。