企业官网建设流程全解析

1. 动态规划与子数组问题概述

动态规划作为算法设计的核心思想之一，在解决各类子数组问题时展现出独特优势。这类问题通常要求我们在给定数组中找到满足特定条件的子数组（连续元素序列），而动态规划通过将原问题分解为相互关联的子问题，避免了重复计算，显著提升了效率。

在实际应用中，从简单的最大子数组和到复杂的环形字符串处理，动态规划解法往往能提供最优时间复杂度（通常为O(n)）的解决方案。本文将系统梳理八类典型子数组问题的动态规划解法，包括状态定义、转移方程建立和边界处理等关键环节，并分享我在刷题和竞赛中积累的实战经验。

2. 基础问题：最大子数组和

2.1 问题定义与暴力解法

给定整数数组nums，找出具有最大和的连续子数组（至少包含一个元素）。例如[-2,1,-3,4,-1,2,1,-5,4]的最大子数组为[4,-1,2,1]，和为6。

暴力解法需要枚举所有子数组起点和终点，计算O(n²)个子数组的和，时间复杂度为O(n³)（直接计算和）或O(n²)（前缀和优化）。这显然无法处理大规模数据。

2.2 动态规划解法

定义dp[i]表示以nums[i]结尾的最大子数组和，转移方程为：

dp[i] = max(nums[i], dp[i-1] + nums[i])

初始化dp[0]=nums[0]，空间复杂度可优化到O(1)：

def maxSubArray(nums): max_sum = curr_sum = nums[0] for num in nums[1:]: curr_sum = max(num, curr_sum + num) max_sum = max(max_sum, curr_sum) return max_sum

关键点：理解dp[i]的定义是"必须包含nums[i]"的局部最优解，全局最优解需要额外变量记录。这种"局部包含"思想贯穿多数子数组问题。

3. 环形数组扩展：环形子数组的最大和

3.1 问题变形

当数组首尾相连时，最大子数组可能跨越数组头尾。例如[5,-3,5]的最大环形子数组是[5,-3,5]整个数组。

3.2 分情况讨论法

最大和子数组要么在常规区间（同问题2），要么跨越头尾。后者等价于总和减去最小子数组和：

def maxSubarraySumCircular(nums): total = sum(nums) max_sum = min_sum = curr_max = curr_min = nums[0] for num in nums[1:]: curr_max = max(num, curr_max + num) max_sum = max(max_sum, curr_max) curr_min = min(num, curr_min + num) min_sum = min(min_sum, curr_min) return max(max_sum, total - min_sum) if max_sum > 0 else max_sum

注意事项：当所有数为负数时，total-min_sum=0会错误返回0，此时应直接返回max_sum。这是边界条件的经典陷阱。

4. 乘积变体：乘积最大子数组

4.1 问题特殊性

乘积与求和的关键区别在于负负得正，因此需要同时维护最大值和最小值：

def maxProduct(nums): max_prod = min_prod = result = nums[0] for num in nums[1:]: candidates = (num, max_prod*num, min_prod*num) max_prod, min_prod = max(candidates), min(candidates) result = max(result, max_prod) return result

4.2 状态转移分析

最大值可能来自：

1. 当前数本身（前序乘积绝对值太小）
2. 前序最大乘积×正数
3. 前序最小乘积×负数（负负得正）

5. 进阶问题：乘积为正数的最长子数组

5.1 双状态设计

定义pos[i]和neg[i]分别表示以nums[i]结尾的乘积为正/负的最长子数组长度：

def getMaxLen(nums): pos = neg = 0 res = 0 for num in nums: if num > 0: pos, neg = pos + 1, (neg + 1 if neg else 0) elif num < 0: pos, neg = (neg + 1 if neg else 0), pos + 1 else: pos = neg = 0 res = max(res, pos) return res

实战技巧：当遇到0时重置计数器，这是典型的"断点"处理模式。类似思想也适用于其他连续性条件的问题。

6. 复杂条件：最长湍流子数组

6.1 问题定义

湍流子数组满足交替的大小关系：A[k] > A[k+1] < A[k+2] > ... 或相反。例如[9,4,2,10,7,8,8,1,9]的最长湍流子数组长度为5([4,2,10,7,8])。

6.2 双状态转移

维护up和down两个状态表示最后一步是上升还是下降：

def maxTurbulenceSize(arr): up = down = res = 1 for i in range(1, len(arr)): if arr[i] > arr[i-1]: up = down + 1 down = 1 elif arr[i] < arr[i-1]: down = up + 1 up = 1 else: up = down = 1 res = max(res, up, down) return res

7. 计数类问题：等差数列划分

7.1 问题分析

计算数组中所有等差子数组的数量。例如[1,2,3,4]有3个等差子数组：[1,2,3], [2,3,4], [1,2,3,4]。

7.2 递推关系

定义dp[i]为以A[i]结尾的等差子数组数量：

def numberOfArithmeticSlices(nums): dp = total = 0 for i in range(2, len(nums)): if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]: dp += 1 total += dp else: dp = 0 return total

优化技巧：实际只需记录前一个dp值，空间复杂度可降至O(1)。这是动态规划的常见空间优化模式。

8. 字符串场景：单词拆分与环形字符串

8.1 单词拆分问题

给定字符串s和单词字典wordDict，判断s是否能被拆分为字典中的单词。例如s="leetcode", wordDict=["leet","code"]返回true。

def wordBreak(s, wordDict): word_set = set(wordDict) dp = [False]*(len(s)+1) dp[0] = True for i in range(1, len(s)+1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True break return dp[-1]

8.2 环形字符串子字符串计数

对于环形字符串，常规解法是将其展开为s+s，然后使用动态规划去重计数。关键在于设计合适的状态表示来避免重复统计。

9. 动态规划解题方法论总结

1. 状态设计原则：

   • 子数组问题通常定义dp[i]为"以第i个元素结尾"的某种最优解
   • 涉及正负变化时需要同时维护最大/最小值（如乘积问题）
   • 环形问题可通过拼接数组或分情况讨论处理

2. 转移方程构建：

   • 分析当前元素与前一状态的关系（包含/不包含）
   • 考虑多种可能的转移路径（如乘积问题的三种情况）
   • 明确边界条件（空数组、全负数等情况）

3. 空间优化技巧：

   • 多数问题只需前一个状态，可用变量代替数组
   • 二维DP问题常可通过滚动数组降维

4. 调试建议：

   • 先写出基础DP解法，再考虑优化
   • 使用小规模测试用例验证边界条件
   • 打印DP表辅助理解状态转移过程

在实际刷题中，我习惯先用具体例子手动推导状态转移过程，再转化为通用代码。对于LeetCode hot100这类高频题库，建议重点掌握这些经典问题的变体和解法模式。