动态规划基础

动态规划(Dynamic Programming, DP)是算法竞赛中非常重要的一种解题技巧，适用于具有【最优子结构】和【重叠子问题】特性的问题。本章将系统介绍动态规划的基础知识和解题思路。

动态规划的核心思想

【定义】动态规划是一种通过将复杂问题分解为更简单的子问题来解决问题的方法，它通过存储子问题的解来避免重复计算。

动态规划的两个关键特性

1. 最优子结构：问题的最优解包含其子问题的最优解
2. 重叠子问题：子问题的解会被重复利用多次

动态规划与分治法的区别

• 分治法：将问题分解为互不相交的子问题，递归解决子问题，然后合并结果
• 动态规划：将问题分解为可能重叠的子问题，自底向上地解决子问题，并保存子问题的结果

动态规划的基本步骤

1. 确定状态表示：明确定义DP数组中每个元素的含义
2. 确定状态转移方程：找出状态之间的递推关系
3. 确定初始状态和边界条件：为DP数组提供初始值
4. 确定计算顺序：通常是自底向上的顺序
5. 计算最终结果：最终答案通常是DP数组中的某个值或者基于DP数组的某种计算

动态规划的实现方式

记忆化搜索（自顶向下）

将递归过程中已计算的子问题结果保存下来，避免重复计算。

// 斐波那契数列的记忆化搜索实现
const int MAXN = 100;
int memo[MAXN]; // 记忆数组，存储已计算的结果

// 初始化为-1，表示未计算
void init() {
    memset(memo, -1, sizeof(memo));
    memo[0] = 0; // 边界情况
    memo[1] = 1; // 边界情况
}

// 带记忆化的递归
int fibonacci(int n) {
    if (n <= 1) return n; // 基本情况处理
    if (memo[n] != -1) return memo[n]; // 已计算，直接返回

    // 计算并保存结果
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
}

递推（自底向上）

直接按照状态转移方程进行递推计算，不使用递归，避免递归开销。

// 斐波那契数列的递推实现
int fibonacci(int n) {
    if (n <= 1) return n; // 处理基础情况

    int dp[MAXN]; // 状态数组
    dp[0] = 0;
    dp[1] = 1;

    // 自底向上计算每个状态
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
    }

    return dp[n];
}

空间优化

对于某些DP问题，可以通过滚动数组或状态压缩等方式降低空间复杂度。

// 斐波那契数列的空间优化实现
int fibonacci(int n) {
    if (n <= 1) return n;

    int prev2 = 0; // f(0)
    int prev1 = 1; // f(1)
    int curr;

    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

动态规划的常见模型

线性DP

状态与前面有限个状态相关，转移方程通常有固定的模式。

例题：最长递增子序列(LIS)

// 最长递增子序列
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的最长递增子序列的长度

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        maxLength = max(maxLength, dp[i]);
    }

    return maxLength;
}

区间DP

状态定义在区间[i,j]上，状态转移通常涉及将区间分割成子区间。

例题：石子合并问题

// 石子合并问题
int mergeStones(vector<int>& stones) {
    int n = stones.size();
    vector<int> sum(n + 1, 0); // 前缀和数组

    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + stones[i - 1];
    }

    // dp[i][j]表示合并区间[i,j]的最小代价
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 枚举区间长度
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            // 枚举分割点
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }

    return dp[1][n];
}

背包DP

处理资源分配类问题，有多种不同类型（01背包、完全背包等）。

例题：01背包问题

// 01背包问题
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            // 不选第i个物品
            dp[i][j] = dp[i - 1][j];

            // 选第i个物品（如果容量允许）
            if (j >= weights[i - 1]) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][capacity];
}

状态压缩DP

使用位运算表示状态集合，适用于集合较小且需要表示子集的情况。

例题：旅行商问题(TSP)

// 旅行商问题简化版
int tsp(vector<vector<int>>& graph) {
    int n = graph.size();
    int all = (1 << n) - 1; // 所有城市都被访问的状态

    // dp[state][i]表示当前在城市i，已访问的城市集合为state时的最短路径长度
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));

    // 初始状态：从城市0出发
    dp[1][0] = 0;

    // 枚举所有状态
    for (int state = 1; state < (1 << n); state++) {
        for (int i = 0; i < n; i++) {
            // 如果城市i不在当前state中，跳过
            if (!(state & (1 << i))) continue;

            // 枚举前一个城市j
            for (int j = 0; j < n; j++) {
                // 如果城市j不在前一个状态中，或者j==i，跳过
                if (i == j || !(state & (1 << j))) continue;

                // 状态转移
                dp[state][i] = min(dp[state][i], dp[state ^ (1 << i)][j] + graph[j][i]);
            }
        }
    }

    // 所有城市都访问后，最后回到城市0
    int result = INT_MAX;
    for (int i = 1; i < n; i++) {
        if (graph[i][0] != INT_MAX) {
            result = min(result, dp[all][i] + graph[i][0]);
        }
    }

    return result;
}

树形DP

在树结构上进行动态规划，状态通常与子树相关。

例题：树的最大独立集

// 树的最大独立集
vector<vector<int>> graph;
vector<int> dp[2]; // dp[0][i]表示不选节点i的最大独立集大小，dp[1][i]表示选择节点i的最大独立集大小

void dfs(int node, int parent) {
    dp[0][node] = 0;
    dp[1][node] = 1; // 选择当前节点

    for (int child : graph[node]) {
        if (child == parent) continue; // 避免向上遍历

        dfs(child, node);

        dp[0][node] += max(dp[0][child], dp[1][child]); // 不选当前节点，子节点可选可不选
        dp[1][node] += dp[0][child]; // 选当前节点，子节点不能选
    }
}

int maxIndependentSet(int n) {
    graph.resize(n + 1);
    dp[0].resize(n + 1);
    dp[1].resize(n + 1);

    // 构建树结构（添加边）...

    dfs(1, -1); // 从根节点开始DFS

    return max(dp[0][1], dp[1][1]);
}

数位DP

按照数位进行动态规划，处理与数字位数相关的计数问题。

例题：计算1到n中数字1的出现次数

// 数位DP：计算1到n中数字1的出现次数
int countDigitOne(int n) {
    if (n <= 0) return 0;

    string s = to_string(n);
    int len = s.length();
    vector<vector<int>> dp(len, vector<int>(len, -1));

    // count(pos, cnt, limit)表示当前在位置pos，已经有cnt个1，是否有上界限制limit
    // 使用记忆化搜索实现数位DP
    function<int(int, int, bool)> count = [&](int pos, int cnt, bool limit) {
        if (pos == len) return cnt;
        if (!limit && dp[pos][cnt] != -1) return dp[pos][cnt];

        int up = limit ? s[pos] - '0' : 9;
        int res = 0;

        for (int i = 0; i <= up; i++) {
            res += count(pos + 1, cnt + (i == 1), limit && i == up);
        }

        if (!limit) dp[pos][cnt] = res;
        return res;
    };

    return count(0, 0, true);
}

动态规划的优化技巧

滚动数组优化

当DP状态只依赖于前一个或几个状态时，可以使用滚动数组降低空间复杂度。

// 01背包的滚动数组优化
int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

单调队列/单调栈优化

适用于某些具有单调性质的DP问题，可以降低时间复杂度。

// 使用单调队列优化的滑动窗口最大值（可用于某些DP转移）
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> q; // 双端队列，存储索引

    for (int i = 0; i < nums.size(); i++) {
        // 移除队首超出窗口范围的元素
        while (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        }

        // 移除队列中所有小于当前元素的值（它们不可能是窗口最大值）
        while (!q.empty() && nums[q.back()] < nums[i]) {
            q.pop_back();
        }

        q.push_back(i);

        // 窗口形成后才开始记录结果
        if (i >= k - 1) {
            result.push_back(nums[q.front()]);
        }
    }

    return result;
}

斜率优化

适用于某些具有特殊形式的DP转移方程，利用斜率来降低时间复杂度。

四边形不等式优化

适用于满足四边形不等式性质的区间DP问题。

实战技巧

1. 分析问题结构：明确问题是否具有最优子结构和重叠子问题特性
2. 从小规模实例开始：先手动解决小规模问题，找出规律
3. 仔细定义状态：状态定义是DP问题的关键
4. 注意边界条件：边界处理往往是DP问题的难点
5. 考虑优化空间：许多DP问题可以通过滚动数组等技巧降低空间复杂度

练习题目推荐

1. POJ 1163 The Triangle (简单线性DP)
2. POJ 1458 Common Subsequence (经典LCS问题)
3. POJ 1651 Multiplication Puzzle (区间DP)
4. POJ 1276 Cash Machine (完全背包问题)
5. POJ 2229 Sumsets (线性DP with 思维)
6. POJ 3254 Corn Fields (状态压缩DP)

常见错误与避坑指南

1. 状态定义不清晰：导致转移方程推导困难
2. 边界条件处理不当：边界是DP问题的常见错误源
3. 循环顺序错误：影响状态依赖关系
4. 忽略特殊情况：要注意极端输入、空集等特殊情况
5. 递推方向错误：自顶向下和自底向上的选择需谨慎
6. 数组越界：DP数组大小预估不足导致越界

通过本章的学习，你应该能够理解动态规划的基本概念和解题思路。在接下来的章节中，我们将深入研究各类动态规划问题的具体应用。