跳到主要内容

动态规划

动态规划是一种通过将复杂问题分解为更小的子问题，并存储子问题的解以避免重复计算的优化技术。它特别适用于具有重叠子问题和最优子结构性质的问题。

核心：​

  • 状态: 动态规划中每个状态代表问题在某个阶段的部分解。

或者说，动态规划的核心，通过将问题分解，然后由初始最优解推到全局最优解。

  • 状态转移方程: 通过状态转移方程，当前状态的值由之前的状态计算得到。

工作原理：​

  • 自底向上: 动态规划通常采用自底向上的方式，从最基本的子问题开始逐步解决，直到解决原问题。

这儿是迭代版本，即通过递推向上求解，例如背包问题的递推。
同样有递归版本，即通过递归将原问题逐步分解为小问题，有的地方会说从顶向下。个人认为，求解过程依然是从低向上。所以务必注意！！！

  • 记忆化: 通过存储子问题的解，避免在后续计算中重复求解相同的子问题。

典型问题​

最长公共子序列问题​

给定两个字符串，找到它们最长的公共子序列（LCS），即在不改变顺序的前提下，在两个字符串中都出现的最大子序列。

例如，输入字符串 X = "ABCBDAB" 和 Y = "BDCABA"，其最长公共子序列为 "BDAB"，长度为 4。

代码示例：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

在这个代码中，dp[i][j] 表示字符串 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列的长度。通过填充 dp 表，最终可以得到 text1 和 text2 的最长公共子序列长度。

爬楼梯问题​

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

这个问题可以看作一个斐波那契数列问题，因为到达第 n 阶的方法数等于到达第 n-1 阶和第 n-2 阶的方法数之和。

代码示例：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
};

在这个代码中，我们利用了滚动数组的思想，只需两个变量 a 和 b 来存储之前的两个状态，从而将空间复杂度从 O(n) 优化为 O(1)。

动态规划的优化​

动态规划的主要优化方向是空间复杂度和状态转移的优化。

  • 空间优化: 对于某些问题，只需保留上一状态或几种状态的信息，可以通过减少维度来优化空间复杂度。
  • 状态压缩: 有些问题可以通过“状态压缩”技术减少所需存储的状态，从而减少空间复杂度。
  • 最优子结构和重叠子问题: 有些问题可以利用贪心算法或分治法进行进一步优化。