Post

LEETCODE - 动态规划

动态规划

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

典型特征：最优子结构、状态转移方程、边界、重叠子问题

求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。

解法

暴力递归解法 - 超时，递归时间复杂度 = 解决一个子问题时间*子问题个数 [[算法 数据结构与算法#时间与空间复杂度]]

带备忘录的递归解法（自顶向下）一般使用一个数组或者一个哈希 map 充当这个备忘录。

自底向上的动态规划，不维护数组/map。只维护依赖的有限个子问题的结果。

树形动态规划

左神提升 5：树型 DP 问题_左程云树 dp 套路时间复杂度-CSDN 博客

337. 打家劫舍 III - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    unordered_map<TreeNode*, vector<int>> dp; // 0 不偷， 1 偷
    void dfs(TreeNode* root) {
        if(!root) return;
        dp[root] = {0, root->val};
        if(root->left){
            dfs(root->left);
            dp[root][0] += max(dp[root->left][0], dp[root->left][1]);
            dp[root][1] += dp[root->left][0];
        }
        if(root->right){
            dfs(root->right);
            dp[root][0] += max(dp[root->right][0], dp[root->right][1]);
            dp[root][1] += dp[root->right][0];
        }
    }

    int rob(TreeNode* root) {
        dfs(root);
        return max(dp[root][0], dp[root][1]);        
    }
};

区间动态规划

它的核心思想是将一个大区间的问题分解为多个小区间的问题，通过求解小区间的最优解，逐步推导出大区间的最优解。

  • 状态定义： 通常用 dp[i][j] 表示区间 [i, j] 上的某个最优值或状态。
  • 状态转移方程： 通过枚举区间内的分割点或决策点 k，将区间 [i, j] 分为 [i, k] 和 [k + 1, j] 两个子区间，然后利用子区间的最优解来更新 dp[i][j]。
  • 边界条件： 通常情况下，长度为 1 的区间（即单个元素）的状态是已知的，作为 DP 的基础。

适用场景：

区间 DP 适用于以下类型的题目：

  • 区间合并/分割问题： 例如石子合并、矩阵链乘法、最优二叉搜索树等。
  • 区间最值问题： 例如最大子段和、最大连续子序列乘积等。
  • 区间计数问题： 例如统计回文子串个数、统计合法括号序列个数等。
  • 其他区间问题： 例如判断是否能通过翻转子区间使两个数组相等。

求解步骤：

  1. 确定状态： 定义 dp[i][j] 的含义，表示区间 [i, j] 上需要求解的量或状态。
  2. 推导状态转移方程： 找到状态之间的递推关系，即 dp[i][j] 如何通过 dp[i][k] 和 dp[k+1][j] (或其他子区间) 的值来计算。
  3. 确定边界条件： 确定长度为 1 的区间的状态值。
  4. 实现代码： 通常使用两层循环，外层循环枚举区间长度，内层循环枚举区间起点。在循环内部，根据状态转移方程计算 dp[i][j] 的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 初始化 dp 数组
for (int i = 1; i <= n; i++) {
    dp[i][i] = ...; // 边界条件
}

// 区间 DP
for (int len = 2; len <= n; len++) { // 枚举区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举区间起点
        int j = i + len - 1; // 区间终点
        for (int k = i; k < j; k++) { // 枚举分割点
            dp[i][j] = ...; // 状态转移方程
        }
    }
}

优化/技巧

四边形不等式优化： 经过四边形不等式优化后，区间 DP 的时间复杂度可以从 O(N^3) 降为 O(N^2)。

滚动数组优化 适用于状态转移方程中，当前状态只依赖于上一行或同一行的状态的情况。

例题

背包问题

[!REFERENCE] > [带你学透 0-1 背包问题！关于背包问题，你不清楚的地方，这里都讲了！动态规划经典问题数据结构与算法_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1cg411g7Y6/?spm_id_from=333.337.search-card.all.click&vd_source=64d148e234fce6362649a575b7d2ccd5)

最长子序列：

具体方法有: Dynamic programming, Greedy + Binary Search

方法一：动态规划

转换问题dp[i]序列， 转移方程dp[i] = max(dp[j]+1) (nums[j] < nums[i])

双重循环，维护 dp 数组，时间复杂度 O（n^2） 空间复杂度 O（n）

方法二：贪心 + 二分查找

https://leetcode.cn/problems/longest-increasing-subsequence/solutions/24173/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2

爬楼梯问题解法总结

爬楼梯问题，减少重复计算（递归有很多重复计算）

  • 重复利用数据 – hashmap

方法一：动态规划

核心思想：

  • 转移方程： f(x) = f(x-1) + f(x-2) 表示爬到第 x 级台阶的方案数等于爬到第 x-1 级和第 x-2 级的方案数之和。
  • 边界条件： f(0) = 1, f(1) = 1
  • 实现方式： 利用滚动数组优化空间复杂度到 O(1)。

时间复杂度： O(n) 空间复杂度： O(1)

方法二：矩阵快速幂

核心思想：

  1. 递推关系转换为矩阵形式：
1

[f(n+1) f(n)] = [1 1; 1 0]^n * [f(1) f(0)]
  1. 快速幂加速计算： 利用快速幂算法加速矩阵的 n 次幂运算。

如何想到使用矩阵快速幂：

  • 问题可转化为求解矩阵的 n 次方形式。
  • 递归式为齐次线性递推式 f(n) = ∑(a_i * f(n-i))，可转化为矩阵递推关系。

时间复杂度： O(log n) 空间复杂度： O(1)

总结：

  • 动态规划适用于 n 较小的情况。
  • 矩阵快速幂适用于 n 较大时，可显著优化时间复杂度。
  • 矩阵快速幂的适用范围更广，可解决多种类型的线性递推问题。

打家劫舍

337. 打家劫舍 III - 力扣（LeetCode）

旅行商问题

旅行商问题 (TSP)

TSP 是一个经典的组合优化问题。给定一系列城市和每对城市之间的距离，目标是找到一条最短的路径，使得旅行商从起点出发，经过每个城市恰好一次，最后回到起点。

TSP 的复杂性

TSP 是一个 NP 困难问题，这意味着不存在多项式时间复杂度的算法可以保证找到最优解。随着城市数量的增加，求解 TSP 的时间复杂度呈指数级增长。

TSP 的求解方法

  1. 精确算法
    • 动态规划 (Held-Karp 算法)： 适用于城市数量较少的情况 (n < 20)。时间复杂度 $O(n^2 \times 2^n)$。
    • 分支限界法： 通过剪枝策略优化搜索过程。在某些情况下，可以比动态规划更快地找到最优解。
  2. 近似算法
    • 贪心算法： 每次选择最近的未访问城市。简单但不能保证最优解。
    • 模拟退火算法： 通过模拟物理退火过程，在解空间中搜索较优解。
    • 遗传算法： 模拟生物进化过程，通过选择、交叉、变异等操作，逐步优化解。

TSP 的相关问题

  1. 哈密顿回路问题 (Hamiltonian Cycle Problem)： 判断是否存在一条经过每个顶点恰好一次的回路。TSP 是哈密顿回路问题的一个特殊情况，要求回路的总权重最小。
  2. 哈密顿路径问题 (Hamiltonian Path Problem)： 判断是否存在一条经过每个顶点恰好一次的路径。与哈密顿回路问题类似，但不要求回到起点。
  3. 最长路径问题 (Longest Path Problem)： 找到图中权重最大的路径。与 TSP 类似，但目标是最大化路径权重。
  4. 车辆路径问题 (Vehicle Routing Problem, VRP)： 多个车辆从仓库出发，为多个客户配送货物，要求最小化总运输成本。VRP 是 TSP 的推广，考虑了车辆容量、时间窗等约束条件。
  5. 中国邮递员问题 (Chinese Postman Problem)： 邮递员需要走遍所有街道，并回到起点。与 TSP 不同，邮递员可以多次经过同一条街道。

Floyd-Warshall 算法

Floyd-Warshall 算法的核心思想是逐步加入中间节点，不断更新任意两点之间的最短路径。具体来说，它维护一个二维数组dist[i][j]，表示从节点i到节点j的最短路径长度。算法通过三层循环，依次考虑每个节点k作为中间节点，更新dist[i][j]的值：

1

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

这个公式的含义是：如果从节点i经过节点k再到节点j的路径比直接从i到j的路径更短，则更新dist[i][j]为更短的路径长度。

解法

1. 动态规划 (Held-Karp 算法) 思路

  • 子问题定义： dp[mask][i] 表示已经访问了集合 mask 中的城市，当前位于城市 i 的最短路径长度。
  • 状态转移： 遍历所有未访问的城市 j，如果从城市 i 到城市 j 有路径，则更新 dp[mask | (1 << j)][j]。
  • 初始状态： dp[1][0] = 0，表示只访问了起点 0，且当前位于起点 0 的路径长度为 0。
  • 最终结果： dp[(1 << n) - 1][0]，表示经过所有城市后回到起点 0 的最短路径长度。

技巧

  • 位运算： 使用位运算来表示城市集合，可以提高效率。例如，mask | (1 << j) 表示在集合 mask 中加入城市 j。
  • 记忆化搜索：

2. 分支限界法 思路

  • 搜索树： 构建一棵搜索树，每个节点表示一个部分解（已经访问了部分城市）。
  • 剪枝： 如果当前部分解的路径长度已经大于等于当前最优解，则剪枝。
  • 限界： 使用一些启发式函数来估计当前部分解的下界，如果下界大于等于当前最优解，则剪枝。
  • 回溯： 如果搜索到一个完整的解，则更新当前最优解。

技巧

  • 启发式函数： 选择合适的启发式函数可以有效地剪枝，提高搜索效率。常见的启发式函数有最近邻点、最小生成树等。
  • 优先队列： 使用优先队列来维护部分解，优先选择最有希望的节点进行扩展
Blogs, Coding
cpp Coding 算法
This post is licensed under CC BY 4.0 by the author.