IO竞赛深入解析：动态规划专题完全指南

安全风信子

发布于 2025-11-12 15:33:01

920

文章被收录于专栏：AI SPPECHAI SPPECH

引言

动态规划（Dynamic Programming，简称DP）是IO竞赛中最常用且最强大的算法思想之一。它能够将复杂问题分解为若干个子问题，通过解决子问题并保存中间结果，最终高效地解决原问题。在IO竞赛中，动态规划类题目占据了很大比例，掌握动态规划的思想和技巧对于取得好成绩至关重要。本文将从动态规划的基础概念出发，深入解析各类动态规划问题的解法，并通过大量实例帮助读者全面掌握这一重要算法思想。

动态规划问题解决流程

问题分析 → 状态定义 → 转移方程推导 → 初始化 → 计算顺序 → 结果获取

步骤	关键内容	注意事项	常见误区
问题分析	识别是否为DP问题	寻找最优子结构和重叠子问题	误判问题类型
状态定义	设计状态表示	状态应包含所有必要信息	状态定义不完整
转移方程推导	建立状态间的关系	考虑所有可能的转移路径	遗漏转移情况
初始化	设置初始状态值	正确处理边界条件	初始值设置错误
计算顺序	确定计算顺序	保证在计算当前状态时，所需的前驱状态已计算	计算顺序错误导致错误结果
结果获取	从最终状态中提取答案	明确目标状态	结果提取错误

目录
├── 第一章：动态规划基础概念
├── 第二章：线性DP
├── 第三章：区间DP
├── 第四章：树形DP
├── 第五章：状态压缩DP
├── 第六章：数位DP
├── 第七章：动态规划优化技巧
└── 第八章：动态规划实战训练

第一章：动态规划基础概念

1.1 动态规划的定义与核心思想

动态规划是一种将原问题分解为相对简单的子问题，先求解子问题，然后从这些子问题的解得到原问题解的方法。动态规划的核心思想是重叠子问题和最优子结构。

重叠子问题：在求解原问题的过程中，会多次重复计算相同的子问题。动态规划通过保存这些子问题的解，避免重复计算，从而提高效率。
最优子结构：原问题的最优解包含了子问题的最优解。也就是说，可以通过子问题的最优解来构造原问题的最优解。

1.2 动态规划与其他算法的区别

算法	核心思想	适用场景	时间复杂度
动态规划	自底向上，保存子问题解	具有重叠子问题和最优子结构的问题	通常为O(n²)或O(n³)
贪心算法	每一步都做出局部最优选择	具有贪心选择性质和最优子结构的问题	通常为O(n)或O(nlogn)
分治法	将问题分解为独立的子问题	子问题相互独立的问题	通常为O(nlogn)或更高

1.3 动态规划的基本步骤

问题分析：判断问题是否适合用动态规划解决，即是否具有重叠子问题和最优子结构。
状态定义：定义状态表示，通常用一个或多个变量来描述问题的当前状态。
转移方程推导：推导状态转移方程，描述如何从已有的子问题解得到当前问题的解。
初始化：设置初始状态的值，包括边界条件。
确定计算顺序：确定状态的计算顺序，确保在计算当前状态时，所需的子问题已经计算完成。
结果获取：根据最终的状态值，计算并返回原问题的解。

1.4 动态规划的基本模型

动态规划问题可以分为多种模型，常见的包括：

线性DP：状态按线性顺序转移的动态规划问题。
区间DP：状态定义在区间上的动态规划问题。
树形DP：在树上进行状态转移的动态规划问题。
状态压缩DP：使用二进制表示状态的动态规划问题。
数位DP：处理数字位的动态规划问题。

第二章：线性DP

2.1 一维线性DP

一维线性DP是最基础的动态规划类型，其状态可以用一个维度的数组来表示。

2.1.1 最大子数组和

问题描述：给定一个整数数组，找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

状态定义：dp[i]表示以第i个元素结尾的最大子数组和。

转移方程：dp[i] = max(nums[i], dp[i-1] + nums[i])

初始化：dp[0] = nums[0]

C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    int maxSum = dp[0];
    
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
        maxSum = max(maxSum, dp[i]);
    }
    
    return maxSum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和：" << maxSubArray(nums) << endl;
    return 0;
}

2.1.2 爬楼梯问题

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

状态定义：dp[i]表示爬到第i阶楼梯的不同方法数。

转移方程：dp[i] = dp[i-1] + dp[i-2]

初始化：dp[1] = 1, dp[2] = 2

C++实现：

#include <iostream>
#include <vector>
using namespace std;

int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

int main() {
    int n = 5;
    cout << "爬到楼顶的不同方法数：" << climbStairs(n) << endl;
    return 0;
}

2.2 二维线性DP

二维线性DP的状态需要用两个维度的数组来表示，通常用于处理二维问题或具有两个状态变量的问题。

2.2.1 最长公共子序列（LCS）

问题描述：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。

状态定义：dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度。

转移方程：

如果text1[i-1] == text2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始化：dp[i][0] = 0，dp[0][j] = 0

C++实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    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];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << "最长公共子序列长度：" << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

2.2.2 最长递增子序列（LIS）

问题描述：给定一个整数数组nums，找到其中最长严格递增子序列的长度。

状态定义：dp[i]表示以nums[i]结尾的最长递增子序列的长度。

转移方程：dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]

初始化：dp[i] = 1

C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int maxLength = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLength = max(maxLength, dp[i]);
    }
    
    return maxLength;
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "最长递增子序列长度：" << lengthOfLIS(nums) << endl;
    return 0;
}

2.3 背包问题

背包问题是动态规划中的经典问题，主要包括0-1背包、完全背包、多重背包等类型。

2.3.1 0-1背包问题

问题描述：给定n个物品，每个物品有重量w[i]和价值v[i]，以及一个容量为C的背包。每个物品只能选择放入或不放入背包，求在不超过背包容量的情况下，能获得的最大价值。

状态定义：dp[i][j]表示前i个物品，背包容量为j时的最大价值。

转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])（如果j >= w[i]）

初始化：dp[0][j] = 0

空间优化后的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack01(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];
}

int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int capacity = 8;
    cout << "0-1背包最大价值：" << knapsack01(weights, values, capacity) << endl;
    return 0;
}

2.3.2 完全背包问题

问题描述：给定n个物品，每个物品有重量w[i]和价值v[i]，以及一个容量为C的背包。每个物品可以选择放入多次，求在不超过背包容量的情况下，能获得的最大价值。

状态定义：dp[i][j]表示前i个物品，背包容量为j时的最大价值。

转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])（如果j >= w[i]）

空间优化后的C++实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int unboundedKnapsack(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 = weights[i]; j <= capacity; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int capacity = 8;
    cout << "完全背包最大价值：" << unboundedKnapsack(weights, values, capacity) << endl;
    return 0;
}

第三章：区间DP

3.1 区间DP的基本概念

区间DP是一种状态定义在区间上的动态规划方法，通常用于解决区间优化问题。区间DP的基本思想是将问题分解为更小的区间，通过求解这些小区间的最优解，合并得到更大区间的最优解，最终得到整个区间的最优解。

区间DP的一般步骤：

定义状态：dp[i][j]表示区间[i,j]上的最优解。
初始化：单个元素的区间dp[i][i] = 初始值。
状态转移：枚举区间长度l，枚举起点i，计算终点j = i + l - 1，然后枚举分割点k，将区间[i,j]分割为[i,k]和[k+1,j]，根据子区间的最优解计算当前区间的最优解。
结果获取：dp[1][n]即为整个区间的最优解。

3.2 经典区间DP问题

3.2.1 石子合并问题

问题描述：有n堆石子排成一排，第i堆石子有a[i]个。每次可以选择相邻的两堆石子合并，合并后新堆的石子数为这两堆石子数的和，合并的代价为新堆的石子数。求将所有石子合并成一堆的最小代价。

状态定义：dp[i][j]表示合并第i堆到第j堆石子的最小代价。

转移方程：dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])，其中i <= k < j

初始化：dp[i][i] = 0

C++实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int stoneGame(vector<int>& stones) {
    int n = stones.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> sum(n + 1, vector<int>(n + 1, 0));
    
    // 预处理前缀和
    vector<int> prefixSum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
    }
    
    // 计算区间和
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            sum[i][j] = prefixSum[j] - prefixSum[i - 1];
        }
    }
    
    // 区间DP
    for (int l = 2; l <= n; l++) { // 区间长度
        for (int i = 1; i + l - 1 <= n; i++) { // 区间起点
            int j = i + l - 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[i][j]);
            }
        }
    }
    
    return dp[1][n];
}

int main() {
    vector<int> stones = {3, 1, 4, 2};
    cout << "石子合并的最小代价：" << stoneGame(stones) << endl;
    return 0;
}

3.2.2 回文子串问题

问题描述：给定一个字符串s，找出其中最长的回文子串的长度。

状态定义：dp[i][j]表示字符串s的子串s[i…j]是否为回文串。

转移方程：dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

初始化：dp[i][i] = true，dp[i][i+1] = (s[i] == s[i+1])

C++实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestPalindromeSubstring(string s) {
    int n = s.length();
    if (n <= 1) return n;
    
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int maxLength = 1;
    int start = 0;
    
    // 初始化单个字符和两个相同字符的情况
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
        if (i < n - 1 && s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            maxLength = 2;
            start = i;
        }
    }
    
    // 区间DP，枚举区间长度
    for (int l = 3; l <= n; l++) {
        for (int i = 0; i + l - 1 < n; i++) {
            int j = i + l - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (l > maxLength) {
                    maxLength = l;
                    start = i;
                }
            }
        }
    }
    
    return maxLength;
}

int main() {
    string s = "babad";
    cout << "最长回文子串长度：" << longestPalindromeSubstring(s) << endl;
    return 0;
}

3.3 区间DP的优化技巧

区间DP的时间复杂度通常为O(n³)，对于较大的n可能会超时。以下是一些常见的区间DP优化技巧：

四边形不等式优化：当状态转移方程满足四边形不等式时，可以将时间复杂度从O(n³)降低到O(n²)。
决策单调性优化：当状态转移方程具有决策单调性时，可以使用分治法或单调队列来优化。
预处理优化：预处理一些常用的中间结果，如区间和、区间最大值等，减少重复计算。
滚动数组优化：对于某些区间DP问题，可以使用滚动数组来优化空间复杂度。

第四章：树形DP

4.1 树形DP的基本概念

树形DP是一种在树上进行状态转移的动态规划方法，主要用于解决树上的优化问题。由于树的结构具有递归性质，树形DP通常采用后序遍历的方式，自底向上地计算每个节点的状态。

树形DP的一般步骤：

选择一个根节点，将树转换为有根树。
定义状态：通常用dp[u]表示以u为根的子树的最优解。
状态转移：通过递归计算子节点的状态，然后根据子节点的状态计算父节点的状态。
结果获取：根节点的状态即为整个树的最优解。

4.2 经典树形DP问题

4.2.1 树的最大独立集

问题描述：给定一棵树，选择一些节点，使得任意两个选中的节点之间没有边相连，求最多可以选择多少个节点。

状态定义：

dp[u][0]表示不选节点u时，以u为根的子树的最大独立集大小。
dp[u][1]表示选节点u时，以u为根的子树的最大独立集大小。

转移方程：

dp[u][0] += max(dp[v][0], dp[v][1])，其中v是u的子节点
dp[u][1] += dp[v][0]，其中v是u的子节点

初始化：dp[u][0] = 0，dp[u][1] = 1

C++实现：

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> tree;
vector<vector<int>> dp;

void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    
    for (int v : tree[u]) {
        if (v != parent) {
            dfs(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
}

int maxIndependentSet(int n) {
    tree.resize(n + 1);
    dp.resize(n + 1, vector<int>(2, 0));
    
    // 构建树（这里假设树的边是1-2, 1-3, 2-4, 2-5）
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[2].push_back(4);
    tree[4].push_back(2);
    tree[2].push_back(5);
    tree[5].push_back(2);
    
    dfs(1, -1);
    return max(dp[1][0], dp[1][1]);
}

int main() {
    int n = 5;
    cout << "树的最大独立集大小：" << maxIndependentSet(n) << endl;
    return 0;
}

4.2.2 树的最小支配集

问题描述：给定一棵树，选择一些节点，使得每个节点要么被选中，要么与一个被选中的节点相邻，求最少需要选择多少个节点。

状态定义：

dp[u][0]表示选中节点u时，以u为根的子树的最小支配集大小。
dp[u][1]表示不选中节点u，但u被其父节点覆盖时，以u为根的子树的最小支配集大小。
dp[u][2]表示不选中节点u，但u被其子节点覆盖时，以u为根的子树的最小支配集大小。

转移方程：

dp[u][0] = 1 + sum(min(dp[v][0], min(dp[v][1], dp[v][2])))，其中v是u的子节点
dp[u][1] = sum(dp[v][2])，其中v是u的子节点
dp[u][2] = min(dp[v][0] + sum(min(dp[v’][0], dp[v’][2])) for v’是u的子节点且v’ != v)，其中v是u的子节点

初始化：dp[u][0] = 1，dp[u][1] = 0，dp[u][2] = INF

C++实现：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

vector<vector<int>> tree;
vector<vector<int>> dp;
const int INF = INT_MAX / 2;

void dfs(int u, int parent) {
    dp[u][0] = 1;
    dp[u][1] = 0;
    dp[u][2] = INF;
    
    int sum = 0;
    int minDiff = INF;
    bool hasChild = false;
    
    for (int v : tree[u]) {
        if (v != parent) {
            hasChild = true;
            dfs(v, u);
            dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
            dp[u][1] += dp[v][2];
            sum += min(dp[v][0], dp[v][2]);
            minDiff = min(minDiff, dp[v][0] - min(dp[v][0], dp[v][2]));
        }
    }
    
    if (hasChild) {
        dp[u][2] = sum + minDiff;
    }
    
    // 处理叶子节点的情况
    if (!hasChild) {
        dp[u][2] = INF;
    }
}

int minVertexCover(int n) {
    tree.resize(n + 1);
    dp.resize(n + 1, vector<int>(3, 0));
    
    // 构建树（这里假设树的边是1-2, 1-3, 2-4, 2-5）
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[2].push_back(4);
    tree[4].push_back(2);
    tree[2].push_back(5);
    tree[5].push_back(2);
    
    dfs(1, -1);
    return min(dp[1][0], dp[1][2]);
}

int main() {
    int n = 5;
    cout << "树的最小支配集大小：" << minVertexCover(n) << endl;
    return 0;
}

4.3 树形DP的优化技巧

树形DP的优化技巧主要包括：

换根DP：当问题需要以不同的节点为根进行计算时，可以使用换根DP来避免重复计算，将时间复杂度从O(n²)降低到O(n)。
长链剖分优化：对于某些树形DP问题，可以使用长链剖分来优化时间复杂度，特别是那些状态与子树高度相关的问题。
树的直径优化：对于与树的直径相关的问题，可以使用两次BFS或DFS来快速计算树的直径，从而优化DP过程。

第五章：状态压缩DP

5.1 状态压缩DP的基本概念

状态压缩DP是一种使用二进制数表示状态的动态规划方法，主要用于解决状态数量较多但可以用二进制位表示的问题。由于二进制数的每一位可以表示一个元素的状态（如选中或未选中），状态压缩DP可以将状态数量从指数级降低到可以处理的范围。

状态压缩DP的一般步骤：

定义状态：用二进制数表示状态，其中每一位表示一个元素的状态。
预处理：预处理一些必要的信息，如状态之间的转移是否合法。
状态转移：根据当前状态和转移规则，计算下一个状态的值。
结果获取：根据最终的状态值，计算并返回原问题的解。

5.2 经典状态压缩DP问题

5.2.1 旅行商问题（TSP）

问题描述：给定n个城市和每对城市之间的距离，求从某个城市出发，经过所有城市恰好一次，最后回到出发城市的最短路径长度。

状态定义：dp[mask][u]表示已经访问过的城市集合为mask（mask的二进制表示中，第i位为1表示城市i已被访问），当前在城市u时的最短路径长度。

转移方程：dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v])，其中v是未访问过的城市。

初始化：dp[1 << u][u] = 0，其中u是出发城市。

C++实现：

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int tsp(vector<vector<int>>& dist, int n) {
    int fullMask = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    // 初始化，从城市0出发
    dp[1 << 0][0] = 0;
    
    // 枚举所有状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            // 如果城市u不在当前状态中，跳过
            if (!(mask & (1 << u))) continue;
            // 如果当前状态不可达，跳过
            if (dp[mask][u] == INT_MAX) continue;
            
            // 枚举下一个要访问的城市v
            for (int v = 0; v < n; v++) {
                // 如果城市v已经访问过，跳过
                if (mask & (1 << v)) continue;
                // 更新状态
                int newMask = mask | (1 << v);
                if (dp[newMask][v] > dp[mask][u] + dist[u][v]) {
                    dp[newMask][v] = dp[mask][u] + dist[u][v];
                }
            }
        }
    }
    
    // 找到回到出发城市的最短路径
    int result = INT_MAX;
    for (int u = 1; u < n; u++) {
        if (dp[fullMask][u] != INT_MAX && dist[u][0] != INT_MAX) {
            result = min(result, dp[fullMask][u] + dist[u][0]);
        }
    }
    
    return result;
}

int main() {
    int n = 4;
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    cout << "旅行商问题的最短路径长度：" << tsp(dist, n) << endl;
    return 0;
}

5.2.2 棋盘覆盖问题

问题描述：给定一个n×n的棋盘，其中有一些格子已经被占据，求用1×2的骨牌覆盖整个棋盘的方案数。

状态定义：dp[i][mask]表示处理到第i行，第i行的状态为mask时的方案数。其中mask的二进制表示中，第j位为1表示第i行第j列的格子已经被覆盖。

转移方程：根据第i-1行的状态和当前行的状态，判断是否可以转移。

初始化：dp[0][0] = 1

C++实现：

#include <iostream>
#include <vector>
using namespace std;

long long chessboardCover(int n, int m, vector<int>& grid) {
    int fullMask = (1 << m) - 1;
    vector<vector<long long>> dp(n + 1, vector<long long>(1 << m, 0));
    dp[0][0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int preMask = 0; preMask < (1 << m); preMask++) {
            if (dp[i-1][preMask] == 0) continue;
            
            // 枚举当前行的状态
            for (int curMask = 0; curMask < (1 << m); curMask++) {
                // 检查当前行的状态是否与前一行的状态兼容
                if ((preMask & curMask) != 0) continue;
                
                // 检查当前行的状态是否与棋盘上的障碍兼容
                if ((curMask & grid[i-1]) != 0) continue;
                
                // 检查当前行的状态是否合法（没有相邻的1）
                if ((curMask & (curMask << 1)) != 0) continue;
                
                dp[i][curMask] += dp[i-1][preMask];
            }
        }
    }
    
    return dp[n][0];
}

int main() {
    int n = 2, m = 3;
    vector<int> grid = {0, 0}; // 0表示没有障碍
    cout << "棋盘覆盖的方案数：" << chessboardCover(n, m, grid) << endl;
    return 0;
}

5.3 状态压缩DP的优化技巧

状态压缩DP的优化技巧主要包括：

位运算优化：充分利用位运算的性质，如&、|、^、<<、>>等，来优化状态的表示和转移。
预处理优化：预处理所有合法的状态和状态转移，减少重复计算。
滚动数组优化：对于某些状态压缩DP问题，可以使用滚动数组来优化空间复杂度。
对称性优化：利用问题的对称性，减少需要计算的状态数量。

第六章：数位DP

6.1 数位DP的基本概念

数位DP是一种处理数字位的动态规划方法，主要用于解决与数字的各位有关的计数问题。数位DP的基本思想是将数字按位分解，逐位处理，同时记录必要的状态，以避免重复计算。

数位DP的一般步骤：

将数字转换为字符串或数组，方便按位处理。
定义状态：通常包括当前处理到的位置、是否受到上界限制、是否有前导零等。
状态转移：根据当前位的数字和之前的状态，计算下一个状态的值。
记忆化搜索：使用记忆化数组来保存已经计算过的状态，避免重复计算。
结果获取：根据最终的状态值，计算并返回原问题的解。

6.2 经典数位DP问题

6.2.1 数字计数问题

问题描述：给定两个整数l和r，求在区间[l, r]内的所有整数中，数字d（0 ≤ d ≤ 9）出现的次数。

状态定义：dp[pos][cnt][limit][lead]表示处理到第pos位，数字d已经出现了cnt次，是否受到上界限制（limit），是否有前导零（lead）时的答案。

转移方程：根据当前位的数字和之前的状态，枚举当前位可以填的数字，计算下一个状态的值。

初始化：递归的起始状态。

C++实现：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> digits;
vector<vector<vector<vector<long long>>>> memo;
int d;

long long dfs(int pos, int cnt, bool limit, bool lead) {
    if (pos == digits.size()) {
        return lead ? 0 : cnt;
    }
    
    if (memo[pos][cnt][limit][lead] != -1) {
        return memo[pos][cnt][limit][lead];
    }
    
    long long res = 0;
    int upper = limit ? digits[pos] : 9;
    
    for (int i = 0; i <= upper; i++) {
        bool newLimit = limit && (i == upper);
        bool newLead = lead && (i == 0);
        int newCnt = cnt;
        if (!newLead) {
            newCnt += (i == d);
        }
        res += dfs(pos + 1, newCnt, newLimit, newLead);
    }
    
    return memo[pos][cnt][limit][lead] = res;
}

long long countDigit(int n, int digit) {
    if (n < 0) return 0;
    if (n == 0) return digit == 0 ? 1 : 0;
    
    digits.clear();
    while (n > 0) {
        digits.push_back(n % 10);
        n /= 10;
    }
    reverse(digits.begin(), digits.end());
    
    d = digit;
    int maxPos = digits.size();
    int maxCnt = maxPos;
    memo.assign(maxPos, vector<vector<vector<long long>>>(maxCnt + 1, 
                vector<vector<long long>>(2, vector<long long>(2, -1))));
    
    return dfs(0, 0, true, true);
}

int main() {
    int l = 1, r = 12;
    int digit = 1;
    long long result = countDigit(r, digit) - countDigit(l - 1, digit);
    cout << "在区间[" << l << ", " << r << "]内数字" << digit << "出现的次数：" << result << endl;
    return 0;
}

6.2.2 回文数计数问题

问题描述：给定两个整数l和r，求在区间[l, r]内的所有回文数的个数。

状态定义：dp[pos][pre][limit][lead]表示处理到第pos位，前一位的数字是pre，是否受到上界限制（limit），是否有前导零（lead）时的回文数个数。

转移方程：根据当前位的数字和之前的状态，枚举当前位可以填的数字，计算下一个状态的值。

初始化：递归的起始状态。

C++实现：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> digits;
vector<vector<vector<vector<long long>>>> memo;
vector<int> palindrome;
int len;

long long dfs(int pos, bool limit, bool lead) {
    if (pos == len) {
        return 1;
    }
    
    if (memo[pos][limit][lead] != -1) {
        return memo[pos][limit][lead];
    }
    
    long long res = 0;
    int upper = limit ? digits[pos] : 9;
    
    if (pos < (len + 1) / 2) {
        // 前半部分，可以自由选择数字
        for (int i = 0; i <= upper; i++) {
            if (lead && i == 0) {
                // 前导零，继续保持前导零状态
                res += dfs(pos + 1, limit && (i == upper), true);
            } else {
                palindrome[pos] = i;
                res += dfs(pos + 1, limit && (i == upper), false);
            }
        }
    } else {
        // 后半部分，需要与前半部分对称
        int mirrorPos = len - 1 - pos;
        int mirrorDigit = palindrome[mirrorPos];
        if (lead) {
            // 全零的情况
            res += 1;
        } else {
            if (mirrorDigit <= upper) {
                res += dfs(pos + 1, limit && (mirrorDigit == upper), false);
            }
        }
    }
    
    return memo[pos][limit][lead] = res;
}

long long countPalindrome(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    
    digits.clear();
    int temp = n;
    while (temp > 0) {
        digits.push_back(temp % 10);
        temp /= 10;
    }
    reverse(digits.begin(), digits.end());
    
    len = digits.size();
    palindrome.assign(len, 0);
    memo.assign(len, vector<vector<long long>>(2, vector<long long>(2, -1)));
    
    long long res = 0;
    // 计算所有长度小于len的回文数
    for (int i = 1; i < len; i++) {
        palindrome.assign(i, 0);
        vector<vector<vector<long long>>> tempMemo(i, vector<vector<long long>>(2, vector<long long>(2, -1)));
        swap(memo, tempMemo);
        len = i;
        res += dfs(0, true, true);
        swap(memo, tempMemo);
    }
    
    // 计算长度等于len的回文数
    len = digits.size();
    palindrome.assign(len, 0);
    memo.assign(len, vector<vector<long long>>(2, vector<long long>(2, -1)));
    res += dfs(0, true, true);
    
    return res;
}

int main() {
    int l = 1, r = 100;
    long long result = countPalindrome(r) - countPalindrome(l - 1);
    cout << "在区间[" << l << ", " << r << "]内的回文数个数：" << result << endl;
    return 0;
}

6.3 数位DP的优化技巧

数位DP的优化技巧主要包括：

记忆化搜索：使用记忆化数组来保存已经计算过的状态，避免重复计算。
状态压缩：合理设计状态，减少状态的数量。
预处理优化：预处理一些常用的中间结果，如数字的各位信息等。
对称性优化：利用回文数等问题的对称性，减少需要计算的状态数量。

第七章：动态规划优化技巧

7.1 空间优化技巧

动态规划的空间优化主要是通过观察状态转移方程，减少存储状态所需的空间。常见的空间优化技巧包括：

滚动数组优化：当状态转移只依赖于前几个状态时，可以使用滚动数组来优化空间复杂度。例如，0-1背包问题的空间优化。
状态压缩优化：当状态的某些维度可以合并或简化时，可以进行状态压缩。例如，某些二维DP问题可以转换为一维DP问题。
单调队列优化：当状态转移方程具有滑动窗口的性质时，可以使用单调队列来优化时间复杂度。例如，滑动窗口最大值问题。

7.2 时间优化技巧

动态规划的时间优化主要是通过优化状态转移过程，减少计算时间。常见的时间优化技巧包括：

四边形不等式优化：当状态转移方程满足四边形不等式时，可以将时间复杂度从O(n³)降低到O(n²)。例如，石子合并问题的优化。
决策单调性优化：当状态转移方程具有决策单调性时，可以使用分治法或单调队列来优化。例如，某些区间DP问题和线性DP问题。
凸包优化：当状态转移方程具有斜率优化的性质时，可以使用凸包技巧来优化。例如，某些具有线性转移方程的DP问题。
快速幂优化：当状态转移可以表示为矩阵乘法时，可以使用快速幂来优化。例如，某些递推问题。

7.3 常见优化方法的应用场景

优化方法	适用场景	时间复杂度优化	空间复杂度优化
滚动数组	状态转移只依赖前几个状态	无	O(n) → O(1)
四边形不等式	区间DP问题，满足四边形不等式	O(n³) → O(n²)	无
决策单调性	满足决策单调性的DP问题	O(n²) → O(n log n)	无
凸包优化	具有线性转移方程的DP问题	O(n²) → O(n)	无
单调队列	具有滑动窗口性质的DP问题	O(n²) → O(n)	无
快速幂	状态转移可表示为矩阵乘法的问题	O(n) → O(log n)	无

第八章：动态规划实战训练

8.1 动态规划题目分类训练

为了更好地掌握动态规划，建议按照不同的类型进行分类训练：

线性DP训练：
- 最大子数组和
- 最长递增子序列
- 最长公共子序列
- 背包问题（0-1背包、完全背包、多重背包）
区间DP训练：
- 石子合并问题
- 回文子串问题
- 括号匹配问题
树形DP训练：
- 树的最大独立集
- 树的最小支配集
- 树的直径问题
状态压缩DP训练：
- 旅行商问题
- 棋盘覆盖问题
- 哈密顿路径问题
数位DP训练：
- 数字计数问题
- 回文数计数问题
- 不含特定数字的数的计数问题

8.2 动态规划解题技巧总结

问题识别：
- 观察问题是否具有重叠子问题和最优子结构
- 尝试将问题分解为更小的子问题
状态设计：
- 状态应包含所有必要的信息，能够完整描述问题的当前状态
- 状态的维度应尽可能少，以减少计算量和存储空间
- 状态的定义应清晰明确，便于推导转移方程
转移方程推导：
- 分析状态之间的关系，找出所有可能的转移路径
- 确保转移方程的正确性，特别是边界条件的处理
- 尝试优化转移方程，减少计算量
代码实现：
- 选择合适的数据结构来存储状态
- 注意初始化的正确性，特别是边界条件
- 确定正确的计算顺序，确保在计算当前状态时，所需的子问题已经计算完成
- 考虑使用记忆化搜索或迭代的方式实现
调试与优化：
- 使用小的测试用例验证代码的正确性
- 分析时间和空间复杂度，寻找优化的空间
- 尝试使用各种优化技巧，如滚动数组、决策单调性等

8.3 动态规划在IO竞赛中的应用案例

8.3.1 IOI 2020 竞赛题目分析

以IOI 2020的部分题目为例，分析动态规划在其中的应用：

题目1：植物 这道题要求选手计算在给定的条件下，能够收获的最大植物数量。这道题可以使用动态规划来解决，通过定义状态表示当前的位置和时间，以及已经收获的植物数量，来推导转移方程。

题目2：连接 这道题要求选手找到一种连接方式，使得连接的总长度最小。这道题可以使用状态压缩动态规划来解决，通过二进制表示已经连接的节点，来计算最小的连接长度。

8.3.2 NOI 2021 竞赛题目分析

以NOI 2021的部分题目为例，分析动态规划在其中的应用：

题目1：路径 这道题要求选手计算在给定的图中，满足某些条件的路径数量。这道题可以使用动态规划来解决，通过定义状态表示当前的节点和已经经过的边的数量，来推导转移方程。

题目2：矩阵 这道题要求选手构造一个满足某些条件的矩阵。这道题可以使用动态规划来解决，通过定义状态表示当前的行和列的状态，来推导转移方程。

结论

动态规划是IO竞赛中最重要的算法思想之一，掌握动态规划对于取得好成绩至关重要。本文从动态规划的基础概念出发，深入解析了各类动态规划问题的解法，并介绍了各种优化技巧。通过系统的学习和训练，选手可以不断提升自己的动态规划解题能力，在IO竞赛中取得更好的成绩。

动态规划学习的价值分布：

基础概念理解(20%) | 状态设计能力(30%) | 转移方程推导(25%) | 优化技巧应用(25%)

互动讨论：

你在学习动态规划的过程中遇到过哪些困难？是如何克服的？
对于动态规划的初学者，你有什么建议？
你认为动态规划中最难掌握的部分是什么？为什么？

参考资料

《算法竞赛入门经典》- 刘汝佳
《算法竞赛进阶指南》- 李煜东
《算法导论》- Thomas H. Cormen等
OI Wiki - https://oi-wiki.org/dp/
Codeforces - https://codeforces.com/
AtCoder - https://atcoder.jp/
LeetCode - https://leetcode.com/
《算法设计与分析》- 王晓东
《动态规划导论》- 王国钧
《计算机算法设计与分析》- 屈婉玲等

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

数组

优化

动态规划

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数组

优化

动态规划