动态规划关键思想与典型应用

在解决算法问题时，动态规划（Dynamic Programming, DP）是一种将复杂问题拆解为重叠子问题并保存中间结果以避免重复计算的策略。其核心在于状态定义和状态转移逻辑的构建。尽管常提到"最优子结构"、"无后效性"等理论概念，但在实际刷题过程中，更有效的方式是结合常见模式进行推导。

状态设计中的无后效性处理

所谓无后效性，是指某一状态一旦确定，后续的决策不会影响该状态的值。若初始状态定义存在依赖未来操作的情况（即有后效），可通过引入更多维度的状态变量来消除。例如，在股票交易类问题中，通过分别记录"持有股票"与"未持有股票"的状态，使得每个状态仅依赖前序状态，从而满足DP要求。

从经验出发寻找状态定义

对于字符串或序列类问题，常见的状态形式往往是基于前缀长度的二维数组。比如设 dp[i][j] 表示第一个序列的前 i 个元素与第二个序列的前 j 个元素之间的某种关系。这种设定虽非普适，但能覆盖大量中等难度题目。

经典模型：0-1背包问题

给定 n 个物品，每个物品有权重 w[i] 和价值 v[i]，以及一个最大承重为 W 的背包，目标是在不超过总重量的前提下，使装入物品的总价值最大。

动态规划解法

使用二维数组 f[i][w] 表示从前 i 个物品中选择、且总重量不超过 w 时的最大价值。

• 状态转移方程：
  f[i][w] = max(f[i-1][w], f[i-1][w - w[i]] + v[i]) （当 w >= w[i]）
  否则：f[i][w] = f[i-1][w]
• 边界条件：
  f[0][*] = 0，表示没有物品可选时价值为0。

最终答案为 f[n][W]。

int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (w[i-1] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][W];
}

分支限界法简述

作为替代方案，分支限界法通过搜索解空间树，并利用上界函数剪枝无效路径。通常按单位价值排序物品，优先尝试高性价比组合。在遍历过程中维护当前最优解，若某分支的理论最大收益仍低于已知解，则提前终止。

编辑距离问题详解

给定两个字符串 s1 和 s2，求将其相互转换所需的最少操作数，允许的操作包括插入、删除、替换字符。

状态含义与转移逻辑

定义 dist[i][j] 为将 s1 的前 i 字符变为 s2 的前 j 字符所需最小步数。

• 初始化：
  dist[i][0] = i（全删），dist[0][j] = j（全插）
• 状态转移：
  若 s1[i-1] == s2[j-1]，则无需操作：dist[i][j] = dist[i-1][j-1]
  否则取三种操作的最小代价加一：
  dist[i][j] = min(dist[i-1][j] + 1, dist[i][j-1] + 1, dist[i-1][j-1] + 1)

int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            }
        }
    }
    return dp[m][n];
}

回溯算法框架与典型场景

回溯法本质上是对决策树的深度优先遍历，适用于求解组合、排列、子集等问题。其基本结构如下：

void backtrack(vector<T>& path, const vector<T>& options) {
    if (isComplete(path)) {
        result.push_back(path);
        return;
    }

    for (const T& choice : options) {
        if (!isValid(choice, path)) continue;
        
        path.push_back(choice);           // 做选择
        backtrack(path, options);
        path.pop_back();                  // 撤销选择
    }
}

常见应用场景

N皇后问题

在 N×N 棋盘上放置 N 个皇后，使其互不攻击。每行只能放一个，逐行尝试各列位置，用集合记录已被占据的列和两条对角线（行−列、行+列为常量）。

图着色问题

给定无向图和 K 种颜色，为每个顶点染色，相邻节点颜色不同。从顶点0开始，尝试每种颜色，递归处理下一节点，失败则回退重试。

子集和判定

判断是否存在子集使得元素和等于目标值。对每个数做"选"或"不选"两种分支，若当前和超过目标则剪枝。

全排列生成

对不含重复元素的数组生成所有排列。维护已选路径和可用元素列表，每次从未选元素中挑一个加入路径，递归完成后移除。

优化技巧

• 剪枝：尽早排除不可能产生合法解的分支，如子集和中累计值已超目标。
• 去重：处理含重复元素的输入时，先排序并在同一层跳过相同值的选择。
• 状态压缩：使用位运算代替布尔数组标记状态，减少空间开销。