LeetCode | 图文详细描述动态规划DP算法及经典题型

LeetCode | 图文详细描述动态规划DP算法及经典题型

引用

CSDN

1.

https://blog.csdn.net/weixin_44649780/article/details/145140378

动态规划（Dynamic Programming，简称DP）是一种通过将问题分解为更小的子问题，逐步求解并存储中间结果，从而避免重复计算的优化方法。它适用于具有重叠子问题和最优子结构的问题。本文将用简单直白的方式，从零开始带你掌握动态规划的精髓。

1. 理论基础

1.1 动态规划的定义

动态规划（Dynamic Programming, DP）是一种通过将问题分解为更小的子问题，逐步求解并存储中间结果，从而避免重复计算的优化方法。它适用于具有重叠子问题和最优子结构的问题。

1.2 动态规划的关键特性

1.2.1 重叠子问题（Overlapping Subproblems）

问题可以分解为许多重复的子问题。例如：
斐波那契数列问题中：
F(n) = F(n-1) + F(n-2)
，子问题重复出现。

1.2.2 最优子结构（Optimal Substructure）

一个问题的最优解由其子问题的最优解构成。例如：
爬楼梯问题：到达第 n 级的总方法数是第 n-1 和第 n-2 级方法数之和。

1.2.3 状态转移方程（State Transition Equation）

描述如何从子问题的解构建更大问题的解，是动态规划的核心。例如：
背包问题的状态转移方程：
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

1.3 动态规划的常见步骤

1.3.1 定义状态（State）
用一个数组或矩阵 dp 表示问题的解，其中 dp[i] 或 dp[i][j] 表示问题在第 i 或 (i,j) 状态的最优解。

1.3.2 状态转移方程（State Transition Equation）
找到子问题与原问题的递推关系，确定状态如何从前一个状态转移。

1.3.3 初始化（Initialization）
确定基础情况，例如： dp[0] 或 dp[0][0] 。

1.3.4 递推计算（Iteration）
通过循环从基础状态逐步递推到目标状态。

1.3.5 返回结果（Result Extraction）
最终返回 dp[n] 或 dp[m][n] 等目标状态的值。

1.4 动态规划的分类

1.4.1 一维动态规划

问题：斐波那契数列、爬楼梯、最小花费爬楼梯
特点：状态数组为一维，dp[i] 表示第 i 步的解。
示例：爬楼梯 dp[i]=dp[i−1]+dp[i−2]

1.4.2 二维动态规划

问题：最短路径问题、背包问题、字符串匹配问题
特点：状态数组为二维矩阵，dp[i][j] 表示二维状态。
示例：最小路径和 dp[i][j]=grid[i][j]+min(dp[i−1][j],dp[i][j−1])

1.4.3 区间动态规划

问题：矩阵链乘积、回文分割问题
特点：状态表示为区间，dp[i][j] 表示从第 i 到第 j 的最优解。
示例：最长回文子序列 dp[i][j]=dp[i+1][j−1]+2if s[i]==s[j]

1.4.4 背包动态规划

问题：01背包问题、完全背包问题
特点：根据背包容量和物品状态转移。
示例：01背包问题 dp[i][w]=max(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])

1.4.5 记忆化递归

问题：与普通动态规划类似，但通过递归解决，配合缓存（如字典或数组）存储中间结果。
特点：自顶向下的方式求解，与自底向上的普通 DP 思路相反。

1.5 优化技巧

1.5.1 空间优化

如果状态转移只依赖前几步状态，可以通过滚动数组将空间复杂度从 O(n) 降低到 O(1)。
示例：斐波那契数列优化版本只用两个变量 prev2 和 prev1 。

1.5.2 压缩维度

对于二维动态规划问题，可以压缩到一维数组进行状态存储。
示例：01 背包问题中，用一维数组存储容量状态。

1.5.3 减少不必要计算

通过提前剪枝，减少动态规划状态的计算范围。

总结：动态规划是一种递推式的优化算法，旨在以最少的计算解决递归性质的问题。

2. 经典例题解析

2.0 基本题型

第 N 个斐波那契数

给定一个正整数 n，任务是找到第 n 个斐波那契数。
斐波那契数列是其中一项是前两项之和的序列。斐波那契数列的前两项是 0 后跟 1。斐波那契数列：0、1、1、2、3、5、8、13、21
斐波那契数定义：

1. F(0)=0
2. F(1)=1
3. F(n)=F(n−1)+F(n−2)（当 n≥2）

# 方法1：递归，时间复杂度：O(2^n) 和 空间复杂度：O(n)
def nth_fibonacci(n):
    if n <= 1:
        return n
    return nth_fibonacci(n-1) + nth_fibonacci(n-2)

# 方法2：自下而上的迭代法，这是计算斐波那契数的最优解法
def nth_fibonacci(n):
    if n <= 1:
        return n
    prev2 = 0
    prev1 = 1
    for _ in range(2, n+1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

# 方法3：自上而下的方法，时间复杂度：O(n) 和 空间复杂度：O(n)
def nth_fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

需掌握题型

• 爬楼梯（Climbing Stairs）
• 最大子数组和（Maximum Subarray, Kadane's Algorithm）
• 最长递增子序列（Longest Increasing Subsequence, LIS）
• 背包问题（01背包、完全背包）
• 编辑距离（Edit Distance）

2.1 简单题型

【Leetcode70】爬楼梯 Climbing Stairs

定义问题：有 n 级楼梯，每次可以走 1 步或 2 步，求到达顶楼的总方法数。

def climb_stairs_optimized(n):
    if n <= 1:
        return 1
    prev2 = 1  # 代表 f(n-2)，初始值为 1
    prev1 = 1  # 代表 f(n-1)，初始值为 1
    for _ in range(2, n+1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

运行过程：
假设 n=5，步骤如下：
Iteration prev2(f(n-2)) prev1(f(n-1)) curr(f(n))
初始值 0 1 -
n=2 1 1 1
n=3 1 2 2
n=4 2 3 3
n=5 3 5 5

最终，prev1 = 5，表示爬到第 5 阶的方法数为 5。

时间与空间复杂度分析
时间复杂度：O(n)

• 无论使用 O(n) 空间还是 O(1) 空间，算法都只需要一次从 2 到 n 的迭代。
  空间复杂度：

1. 使用数组 O(n)：需要额外数组存储中间结果。
2. 空间优化 O(1)：仅存储两个变量，节省了内存。

2.2 中等题型

【Leetcode53】最大子数组(Maximum Subarray)

问题：给定一个整数数组，找到 nums 子数组，并返回其总和

def max_subarray(nums):
    current_sum = max_sum = nums[0]
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    return max_sum

运行过程：
数组：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
元素 current_sum 更新规则 current_sum max_sum
-2 初始值 -2 -2
1 max(1, -2 + 1) = 1 1 1
-3 max(-3, 1 - 3) = -2 -2 1
4 max(4, -2 + 4) = 4 4 4
-1 max(-1, 4 - 1) = 3 3 4
2 max(2, 3 + 2) = 5 5 5
1 max(1, 5 + 1) = 6 6 6
-5 max(-5, 6 - 5) = 1 1 6
4 max(4, 1 + 4) = 5 5 6

最优性分析：

• 时间复杂度最优：只需一次遍历，时间复杂度为 O(n)。
• 空间复杂度最低：不需要额外存储，只用常数级变量，空间复杂度为 O(1)。
• 适用性强：适用于有正负数混合的数组，且数组长度为 1 时依然有效。

【Leetcode64】网格中的最小路径/最小路径总和（Minimux Path Sum）

给定一个2d矩阵 cost[][]，任务是计算从（0， 0）到（m，n）的最小成本路径。矩阵的每个像元都表示求解该像元的成本。到达路径的总费用（米，N）是该路径（包括源和目标）上所有费用的总和。我们只能从给定的单元格依次、向右和对角线依次遍历单元格，即从给定的单元格开始单元格 （i，j）、单元格（i+1，j）、（i，j+1）和（i+1，j+1）可以遍历。

问题分析：
要找到从左上角 (0, 0) 到右下角 (m, n) 的最小成本路径，可以使用动态规划。动态规划是一种有效的方法，它通过记录每一步的最优结果，避免了重复计算。

动态规划的最优解
我们定义一个辅助的动态规划矩阵 dp，其中 dp[i][j] 表示从 (0, 0) 到 (i, j) 的最小成本路径。转移方程如下：
dp[i][j]=cost[i][j]+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])

def min_cost_path(cost, m, n):
    rows = len(cost)
    cols = len(cost[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = cost[0][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j-1] + cost[0][j]
    for i in range(1, rows):
        dp[i][0] = dp[i-1][0] + cost[i][0]
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = cost[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

最优性分析：

时间复杂度：O(m×n)

• 需要遍历整个矩阵，每个单元格计算一次。

空间复杂度：O(m×n)

• 需要额外的 dp 矩阵存储中间结果。