线性动态规划（一维状态 / 顺序转移）经典问题解析与代码实现
动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中广泛应用的方法。它通过将复杂问题分解为更小的子问题，并存储这些子问题的解，从而避免重复计算，提高算法效率。线性动态规划是一种特殊的动态规划方法，它涉及一维状态和顺序转移。本文将围绕线性动态规划的经典问题进行解析，并通过代码实现展示其应用。
一、线性动态规划概述
线性动态规划通常涉及以下特点：
1. 子问题重叠：子问题之间具有重叠性，即子问题的解会被多次使用。
2. 最优子结构：问题的最优解包含其子问题的最优解。
3. 状态转移方程：通过子问题的解来构建原问题的解。
4. 一维状态：状态通常表示为一维数组，每个元素对应一个子问题的解。
二、经典问题解析
1. 最长递增子序列（LIS）
问题描述：给定一个无序数组，找出其中最长的递增子序列的长度。
状态转移方程：设`dp[i]`表示以`nums[i]`结尾的最长递增子序列的长度，则`dp[i] = max(dp[i], dp[j] + 1)`，其中`j < i`且`nums[j] < nums[i]`。
代码实现：
python
def lengthOfLIS(nums):
if not nums:
return 0
dp = [1] len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums)) 输出: 4
2. 最小路径和
问题描述：给定一个二维数组，找出从左上角到右下角的最小路径和。
状态转移方程：设`dp[i][j]`表示到达`(i, j)`的最小路径和，则`dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + nums[i][j]`。
代码实现：
python
def minPathSum(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
dp = [[0] n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]
示例
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print(minPathSum(grid)) 输出: 7
3. 房屋偷盗
问题描述：你是一个专业的偷盗者，计划偷窃一系列房屋，每间房屋只能偷窃一次。计算你能偷窃到的最大金额。
状态转移方程：设`dp[i]`表示偷窃到第`i`间房屋的最大金额，则`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`。
代码实现：
python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
示例
nums = [2, 7, 9, 3, 1]
print(rob(nums)) 输出: 12
三、总结
本文介绍了线性动态规划的基本概念和经典问题，并通过代码实现了最长递增子序列、最小路径和和房屋偷盗等问题的解决方案。线性动态规划在解决具有重叠子问题和最优子结构的问题时具有显著优势，是算法设计中不可或缺的一部分。在实际应用中，通过合理设计状态转移方程和状态数组，可以有效地解决各种复杂问题。
Comments NOTHING