admin 的博客
acm005 动态规划算法详解：从基础到实战
admin LV 1 SU @ 2025-11-17 11:27:27

动态规划算法详解：从基础到实战

1. 动态规划基本概念

动态规划(Dynamic Programming)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它主要用于解决具有重叠子问题和最优子结构性质的问题。

1.1 动态规划的核心思想

三个基本特征：

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：子问题会被重复计算多次
无后效性：当前状态确定后，后续决策不受之前决策的影响

两种实现方式：

自顶向下：记忆化搜索（递归+记忆）
自底向上：递推计算（迭代）

2. 经典动态规划问题

2.1 数塔问题

问题描述：从数塔顶部出发，在每一节点选择向左或向右走，求到达底层的最大路径和。

状态定义：dp[i][j]表示从第i行第j列出发到达底层的最大路径和

状态转移方程：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + tower[i][j]

代码实现：

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

int numberTower(vector<vector<int>>& tower) {
    int n = tower.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // 初始化底层
    for (int j = 0; j < n; j++) {
        dp[n-1][j] = tower[n-1][j];
    }
    
    // 自底向上计算
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + tower[i][j];
        }
    }
    
    return dp[0][0];
}

// 空间优化版本
int numberTower_optimized(vector<vector<int>>& tower) {
    int n = tower.size();
    vector<int> dp(tower[n-1]);  // 初始化为最后一层
    
    for (int i = n-2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = max(dp[j], dp[j+1]) + tower[i][j];
        }
    }
    
    return dp[0];
}

int main() {
    vector<vector<int>> tower = {
        {9},
        {12, 15},
        {10, 6, 8},
        {2, 18, 9, 5},
        {19, 7, 10, 4, 16}
    };
    
    cout << "最大路径和: " << numberTower(tower) << endl;
    return 0;
}

2.2 最长递增子序列(LIS)

问题描述：给定一个序列，找到最长的递增子序列的长度。

状态定义：dp[i]表示以第i个元素结尾的最长递增子序列长度

状态转移方程：

dp[i] = max(dp[j]) + 1, 对于所有 j < i 且 nums[j] < nums[i]

代码实现：

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

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int n = nums.size();
    vector<int> dp(n, 1);  // 每个元素本身至少构成长度为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;
}

// 优化版本：O(n log n)
int lengthOfLIS_optimized(vector<int>& nums) {
    vector<int> tail;  // tail[i]表示长度为i+1的递增子序列的最小尾元素
    
    for (int num : nums) {
        // 二分查找插入位置
        auto it = lower_bound(tail.begin(), tail.end(), num);
        if (it == tail.end()) {
            tail.push_back(num);  // 比所有尾元素都大，延长序列
        } else {
            *it = num;  // 替换第一个大于等于num的元素
        }
    }
    
    return tail.size();
}

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

2.3 免费馅饼问题

问题描述：在0-10的坐标轴上接馅饼，每秒只能移动1米，求最多能接多少馅饼。

分析：将时间作为一维，坐标作为另一维，转化为数塔类问题。

代码实现：

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

int freePie() {
    int n;
    while (cin >> n && n) {
        const int MAX_TIME = 100000;
        const int MAX_POS = 11;
        
        vector<vector<int>> pie(MAX_TIME, vector<int>(MAX_POS, 0));
        int maxTime = 0;
        
        // 读入数据
        for (int i = 0; i < n; i++) {
            int x, t;
            cin >> x >> t;
            pie[t][x]++;
            maxTime = max(maxTime, t);
        }
        
        // DP数组：dp[t][x]表示在t时刻位于x位置能接到的最大馅饼数
        vector<vector<int>> dp(maxTime + 1, vector<int>(MAX_POS, -1));
        
        // 初始化起始位置
        dp[0][5] = 0;
        
        // 时间递推
        for (int t = 1; t <= maxTime; t++) {
            for (int x = 0; x < MAX_POS; x++) {
                // 可以从三个方向过来：x-1, x, x+1
                for (int dx = -1; dx <= 1; dx++) {
                    int prevX = x + dx;
                    if (prevX >= 0 && prevX < MAX_POS && dp[t-1][prevX] != -1) {
                        dp[t][x] = max(dp[t][x], dp[t-1][prevX] + pie[t][x]);
                    }
                }
            }
        }
        
        // 找最大值
        int result = 0;
        for (int x = 0; x < MAX_POS; x++) {
            result = max(result, dp[maxTime][x]);
        }
        
        cout << result << endl;
    }
    return 0;
}

2.4 胖老鼠的速度问题

问题描述：找到体重递增且速度递减的最长子序列。

分析思路：

按体重递增排序
在排序后的序列中找速度的最长递减子序列

代码实现：

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

struct Mouse {
    int weight;
    int speed;
    int index;  // 原始索引
};

bool compareWeight(const Mouse& a, const Mouse& b) {
    return a.weight < b.weight;  // 按体重递增排序
}

void fatMouseSpeed() {
    vector<Mouse> mice;
    Mouse m;
    int count = 0;
    
    // 读入数据
    while (cin >> m.weight >> m.speed) {
        m.index = ++count;
        mice.push_back(m);
    }
    
    // 按体重排序
    sort(mice.begin(), mice.end(), compareWeight);
    
    int n = mice.size();
    vector<int> dp(n, 1);  // 以每个老鼠结尾的最长序列长度
    vector<int> prev(n, -1);  // 前驱指针，用于输出序列
    
    int maxLen = 0, endIndex = -1;
    
    // 求速度的最长递减子序列
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (mice[j].weight < mice[i].weight && 
                mice[j].speed > mice[i].speed) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
        
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            endIndex = i;
        }
    }
    
    // 输出结果
    cout << maxLen << endl;
    vector<int> result;
    while (endIndex != -1) {
        result.push_back(mice[endIndex].index);
        endIndex = prev[endIndex];
    }
    
    // 逆序输出
    for (int i = result.size() - 1; i >= 0; i--) {
        cout << result[i] << endl;
    }
}

2.5 最少拦截系统

问题描述：导弹高度依次飞来，每个拦截系统只能拦截不高于前一次高度的导弹，求最少需要多少拦截系统。

分析：根据Dilworth定理，最少链划分等于最长反链长度，即求最长上升子序列的长度。

代码实现：

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

int minInterceptSystems(vector<int>& heights) {
    // 直接求最长上升子序列的长度
    return lengthOfLIS(heights);
}

// 贪心解法
int minInterceptSystems_greedy(vector<int>& heights) {
    vector<int> systems;  // 每个系统当前拦截的最低高度
    
    for (int height : heights) {
        // 查找可以拦截该导弹的系统
        auto it = lower_bound(systems.begin(), systems.end(), height, greater<int>());
        if (it == systems.end()) {
            // 需要新系统
            systems.push_back(height);
        } else {
            // 更新该系统的最低拦截高度
            *it = height;
        }
    }
    
    return systems.size();
}

int main() {
    vector<int> heights = {389, 207, 155, 300, 299, 170, 158, 65};
    cout << "最少需要拦截系统: " << minInterceptSystems(heights) << endl;
    return 0;
}

2.6 搬寝室问题

问题描述：搬n件物品，每次左手右手各一件，疲劳度与重量差的平方成正比，求搬m趟的最小疲劳度。

分析思路：

对物品重量排序
每次搬的两件物品一定是相邻的（可证明）
定义dp[i][j]为前i件物品搬j趟的最小疲劳度

状态转移方程：

dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + (w[i]-w[i-1])^2)

代码实现：

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

int moveDormitory(int n, int m, vector<int>& weights) {
    if (2 * m > n) return 0;  // 不可能搬完
    
    sort(weights.begin(), weights.end());
    
    // dp[i][j]: 前i件物品搬j趟的最小疲劳度
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX / 2));
    
    // 初始化：搬0趟疲劳度为0
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (2 * j > i) continue;  // 物品不够
            
            int diff = weights[i-1] - weights[i-2];
            int cost = diff * diff;
            
            // 两种选择：不选第i件物品，或选第i和i-1件物品作为一趟
            dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + cost);
        }
    }
    
    return dp[n][m];
}

// 空间优化版本
int moveDormitory_optimized(int n, int m, vector<int>& weights) {
    if (2 * m > n) return 0;
    
    sort(weights.begin(), weights.end());
    
    vector<int> dp(m + 1, INT_MAX / 2);
    dp[0] = 0;
    
    for (int i = 2; i <= n; i++) {
        for (int j = min(m, i / 2); j >= 1; j--) {
            int diff = weights[i-1] - weights[i-2];
            int cost = diff * diff;
            
            dp[j] = min(dp[j], dp[j-1] + cost);
        }
    }
    
    return dp[m];
}

int main() {
    int n = 2, m = 1;
    vector<int> weights = {1, 3};
    cout << "最小疲劳度: " << moveDormitory(n, m, weights) << endl;
    return 0;
}

3. 动态规划解题技巧

3.1 状态设计原则

状态要能描述问题的特征
状态空间要尽量小
要满足最优子结构和无后效性

3.2 常见优化技巧

3.2.1 滚动数组

// 普通DP
vector<vector<int>> dp(n, vector<int>(m));

// 滚动数组优化
vector<int> dp_old(m), dp_new(m);
for (int i = 1; i < n; i++) {
    swap(dp_old, dp_new);
    // 计算dp_new
}

3.2.2 状态压缩

// 当状态可以用位表示时
for (int mask = 0; mask < (1 << n); mask++) {
    // 处理状态mask
}

3.2.3 四边形不等式优化

用于优化区间DP的决策单调性。

3.3 调试技巧

打印DP表：观察状态转移过程
边界测试：测试小规模数据
对比暴力：与暴力解法对比验证

4. 动态规划分类

4.1 线性DP

最长公共子序列(LCS)
最长递增子序列(LIS)
编辑距离

4.2 区间DP

矩阵连乘
石子合并
多边形三角剖分

4.3 树形DP

树的最大独立集
树的重心
树的直径

4.4 状态压缩DP

旅行商问题(TSP)
铺砖问题

5. 学习建议

理解思想：掌握动态规划的核心思想比记忆模板更重要
多练习：从简单题目开始，逐步提高难度
总结归纳：同类问题归纳总结，形成解题模式
思考优化：在AC的基础上思考如何优化时间和空间

通过系统学习动态规划，你能够解决许多复杂的优化问题，这是算法竞赛和面试中的重要考点。坚持练习，你会发现动态规划其实并不难，而是充满美感和智慧。

acm005 动态规划算法详解：从基础到实战

动态规划算法详解：从基础到实战

1. 动态规划基本概念

1.1 动态规划的核心思想

2. 经典动态规划问题

2.1 数塔问题

2.2 最长递增子序列(LIS)

2.3 免费馅饼问题

2.4 胖老鼠的速度问题

2.5 最少拦截系统

2.6 搬寝室问题

3. 动态规划解题技巧

3.1 状态设计原则

3.2 常见优化技巧

3.2.1 滚动数组

3.2.2 状态压缩

3.2.3 四边形不等式优化

3.3 调试技巧

4. 动态规划分类

4.1 线性DP

4.2 区间DP

4.3 树形DP

4.4 状态压缩DP

5. 学习建议

登录