当前位置：首页 > news >正文

动态规划（5）：线性动态规划

news 来源：原创 2025/7/17 21:45:11

引言

所谓线性动态规划，通常指状态定义和转移具有线性结构的动态规划问题，其状态通常可以用一维数组表示，状态转移主要依赖于相邻或前面有限个状态。这类问题的特点是状态空间呈线性排列，每个状态只与有限个前置状态相关，使得问题结构相对简单，更容易理解和掌握。

一维DP问题解析

一维DP的特点

一维动态规划问题具有以下几个显著特点：

状态表示简单：通常用一维数组dp[i]表示与索引i相关的某种性质或结果。
状态转移局部化：新状态通常只依赖于有限个前置状态，如dp[i-1]、dp[i-2]等。
计算顺序明确：大多数情况下，从小到大（或从大到小）按索引顺序计算。
空间复杂度可优化：由于状态转移的局部性，通常可以优化空间复杂度。

一维DP的一般解题框架

解决一维DP问题通常遵循以下框架：

确定状态定义：明确dp[i]表示什么，这是解题的关键。
推导状态转移方程：分析dp[i]与前面状态的关系，得出转移方程。
确定初始状态：设置dp数组的初始值，通常是dp[0]或dp[1]。
确定计算顺序：通常是从小到大的顺序。
计算最终结果：根据问题要求，确定最终结果是dp数组中的某个值或是对dp数组的某种计算。

一维DP问题的分类

一维DP问题可以根据状态转移的特点进一步分类：

前缀/后缀型：当前状态依赖于之前所有状态的某种统计或极值。
- 例如：前缀和、前缀最大值等。
区间型：当前状态依赖于特定区间内的状态。
- 例如：滑动窗口最大值、区间DP等。
跳跃型：当前状态可以从多个不连续的前置状态转移而来。
- 例如：跳跃游戏、青蛙跳台阶等。
博弈型：涉及到多方博弈的状态转移。
- 例如：Nim游戏、石子游戏等。

一维DP的思考方法

解决一维DP问题时，可以采用以下思考方法：

定义清晰：确保dp[i]的定义明确、具体，避免模糊不清。
考虑边界：仔细处理边界情况，如i=0、i=1等特殊情况。
归纳推理：通过小规模实例，归纳状态转移规律。
正确性验证：通过手动计算小规模实例，验证状态转移方程的正确性。
优化思考：考虑是否可以优化时间复杂度或空间复杂度。

经典问题：最长递增子序列

最长递增子序列（Longest Increasing Subsequence, LIS）是线性动态规划中的经典问题，它要求在一个给定的数字序列中，找到一个最长的子序列，使得这个子序列中的数字按照从小到大的顺序排列。

问题描述

给定一个无序的整数数组nums，找到其中最长上升子序列的长度。

示例：

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是4。

问题分析

这个问题的关键在于理解"子序列"的概念：子序列不要求连续，只要保持原序列中的相对顺序即可。

我们可以使用动态规划来解决这个问题：

定义状态：dp[i]表示以nums[i]结尾的最长递增子序列的长度。
状态转移：对于每个位置i，我们需要找出所有满足j < i且nums[j] < nums[i]的位置j，然后取dp[j]的最大值加1。
初始状态：每个元素自身就是一个长度为1的递增子序列，所以初始化dp[i] = 1。
最终结果：dp数组中的最大值。

动态规划解法

def lengthOfLIS(nums):if not nums:return 0n = len(nums)dp = [1] * n  # 初始化为1，因为每个元素自身就是一个长度为1的递增子序列for i in range(1, n):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

解法分析

时间复杂度：O(n²)，其中n是数组的长度。我们需要两层循环来填充dp数组。
空间复杂度：O(n)，需要一个长度为n的dp数组。

优化解法：二分查找

上述解法的时间复杂度是O(n²)，对于大规模数据可能会超时。我们可以使用二分查找优化到O(n log n)：

def lengthOfLIS(nums):if not nums:return 0tails = []  # tails[i]表示长度为i+1的递增子序列的最小结尾值for num in nums:# 二分查找num应该插入的位置left, right = 0, len(tails)while left < right:mid = (left + right) // 2if tails[mid] < num:left = mid + 1else:right = mid# 如果找到了合适的位置，更新tailsif left == len(tails):tails.append(num)else:tails[left] = numreturn len(tails)

优化解法分析

时间复杂度：O(n log n)，其中n是数组的长度。对于每个元素，我们使用二分查找，时间复杂度为O(log n)。
空间复杂度：O(n)，需要一个长度最多为n的tails数组。

问题变形与扩展

最长递减子序列：将条件改为nums[i] < nums[j]即可。
最长非递减子序列：将条件改为nums[i] >= nums[j]。
最长摆动子序列：要求子序列中的元素交替增减。
俄罗斯套娃信封问题：二维版本的最长递增子序列。

经典问题：最大子数组和

最大子数组和（Maximum Subarray Sum）是另一个经典的线性动态规划问题，它要求在一个给定的整数数组中，找到一个具有最大和的连续子数组。

问题描述

给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

问题分析

这个问题的关键在于理解"连续子数组"的概念：子数组必须是原数组中的连续部分。

我们可以使用动态规划来解决这个问题：

定义状态：dp[i]表示以nums[i]结尾的连续子数组的最大和。
状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])，即要么从当前元素开始新的子数组，要么将当前元素加入前面的子数组。
初始状态：dp[0] = nums[0]。
最终结果：dp数组中的最大值。

动态规划解法

def maxSubArray(nums):if not nums:return 0n = len(nums)dp = [0] * ndp[0] = nums[0]for i in range(1, n):dp[i] = max(nums[i], dp[i-1] + nums[i])return max(dp)

引言

一维DP问题解析

一维DP的特点

一维DP的一般解题框架

一维DP问题的分类

一维DP的思考方法

经典问题：最长递增子序列

问题描述

问题分析

动态规划解法

解法分析

优化解法：二分查找

优化解法分析

问题变形与扩展

经典问题：最大子数组和

问题描述

问题分析

动态规划解法

相关文章：