C09第2章动态规划

admin

动态规划是一种通过将复杂问题分解为重叠子问题，并存储子问题解（避免重复计算）来高效解决问题的方法。其核心是状态定义和状态转移方程。
1. 0-1 背包问题
实际应用：资源分配、投资决策等场景，在有限资源下选择最优组合。
状态定义：dp[j] 表示容量为 j 的背包能装入的最大价值。
状态转移：dp[j] = max(dp[j], dp[j - w] + v)（对第 i 件物品，选或不选）。
优化：使用一维数组并从后往前更新，将空间复杂度从 O (nC) 降至 O (C)。

2. 最长公共子序列 (LCS)
实际应用：字符串相似度比较（如 DNA 序列比对、版本控制中的差异分析）。
状态定义：dp[j] 表示字符串 s1[0..i-1] 和 s2[0..j-1] 的 LCS 长度。
状态转移：
若 s1[i-1] == s2[j-1]，则 dp[j] = dp[i-1][j-1] + 1；
否则 dp[j] = max(dp[i-1][j], dp[j-1])。

3. Floyd-Warshall 最短路径算法
实际应用：交通网络规划、路由算法等，求任意两点间的最短路径。
状态定义：dist[j] 表示顶点 i 到 j 的最短路径长度。
状态转移：dist[j] = min(dist[j], dist[k] + dist[k][j])（通过中间顶点 k 优化路径）。
特点：时间复杂度 O (n³)，适合求解小规模图的全源最短路径。

4. 最大子数组和（Kadane 算法）
实际应用：股票价格分析（最大收益区间）、信号处理等。
状态定义：prev 表示以当前元素结尾的最大子数组和。
状态转移：prev = max(nums, prev + nums)（要么从当前元素重新开始，要么加入前一个子数组）。
优化：仅用变量保存前一个状态，空间复杂度 O (1)。

5. 爬楼梯问题
实际应用：步数规划、组合计数等简单递推问题。
状态定义：dp 表示爬上 i 阶台阶的方法数。
状态转移：dp = dp[i-1] + dp[i-2]（最后一步要么爬 1 阶，要么爬 2 阶）。
优化：仅保存前两个状态，空间复杂度 O (1)。

动态规划的核心思想总结
重叠子问题：问题可以分解为重复出现的子问题，避免重复计算。
最优子结构：问题的最优解包含子问题的最优解。
状态转移：用数学公式描述子问题之间的关系。
空间优化：通过观察状态依赖关系，减少存储的状态数量（如用一维数组替代二维数组）。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>

using namespace std;

/**
 * 应用1：0-1背包问题
 * 有n件物品，每件物品有重量w和价值v，背包容量为C
 * 求能装入背包的最大价值（每件物品只能选一次）
 */
int knapsack01(const vector<int>& w, const vector<int>& v, int C) {
    int n = w.size();
    if (n == 0 || C <= 0) return 0;
    
    // dp[j]表示前i件物品放入容量为j的背包的最大价值
    // 优化空间：只需一维数组，从后往前更新
    vector<int> dp(C + 1, 0);
    
    for (int i = 0; i < n; ++i) {
        // 从后往前更新，避免重复使用同一物品
        for (int j = C; j >= w; --j) {
            // 状态转移方程：选或不选第i件物品
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    
    return dp[C];
}

/**
 * 应用2：最长公共子序列(LCS)
 * 给定两个字符串，求它们最长的公共子序列长度
 * 子序列：不要求连续，但顺序一致
 */
int longestCommonSubsequence(const string& s1, const string& s2) {
    int m = s1.size();
    int n = s2.size();
    
    // dp[j]表示s1[0..i-1]和s2[0..j-1]的LCS长度
    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 (s1[i - 1] == s2[j - 1]) {
                // 字符相同，LCS长度加1
                dp[j] = dp[i - 1][j - 1] + 1;
            } else {
                // 字符不同，取子问题的最大值
                dp[j] = max(dp[i - 1][j], dp[j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

/**
 * 应用3：最短路径问题（Floyd-Warshall算法）
 * 求图中所有顶点对之间的最短路径
 */
void floydWarshall(const vector<vector<int>>& graph, vector<vector<int>>& dist) {
    int n = graph.size();
    
    // 初始化距离矩阵
    dist = graph;
    
    // k为中间顶点
    for (int k = 0; k < n; ++k) {
        // i为起点
        for (int i = 0; i < n; ++i) {
            // j为终点
            for (int j = 0; j < n; ++j) {
                // 状态转移：经过k是否能缩短i到j的距离
                if (dist[k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[j] = min(dist[j], dist[k] + dist[k][j]);
                }
            }
        }
    }
}

/**
 * 应用4：最大子数组和（ Kadane算法）
 * 给定整数数组，找到具有最大和的连续子数组
 */
int maxSubarraySum(const vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int n = nums.size();
    // dp表示以nums结尾的最大子数组和
    // 优化：只需保存前一个状态
    int prev = nums[0];
    int max_sum = prev;
    
    for (int i = 1; i < n; ++i) {
        // 状态转移：要么加入前一个子数组，要么重新开始
        prev = max(nums, prev + nums);
        max_sum = max(max_sum, prev);
    }
    
    return max_sum;
}

/**
 * 应用5：爬楼梯问题
 * 每次可以爬1或2个台阶，求爬上n个台阶的不同方法数
 */
int climbStairs(int n) {
    if (n <= 2) return n;
    
    // dp表示爬上i个台阶的方法数
    // 优化：只需保存前两个状态
    int prev_prev = 1;  // 1阶台阶
    int prev = 2;       // 2阶台阶
    
    for (int i = 3; i <= n; ++i) {
        // 状态转移：最后一步要么爬1阶，要么爬2阶
        int curr = prev_prev + prev;
        prev_prev = prev;
        prev = curr;
    }
    
    return prev;
}

int main() {
    // 测试应用1：0-1背包
    cout << "=== 应用1：0-1背包问题 ===" << endl;
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int capacity = 8;
    cout << "物品重量: ";
    for (int w : weights) cout << w << " ";
    cout << endl;
    cout << "物品价值: ";
    for (int v : values) cout << v << " ";
    cout << endl;
    cout << "背包容量: " << capacity << endl;
    cout << "最大价值: " << knapsack01(weights, values, capacity) << endl << endl;
    
    // 测试应用2：最长公共子序列
    cout << "=== 应用2：最长公共子序列 ===" << endl;
    string s1 = "ABCBDAB";
    string s2 = "BDCAB";
    cout << "字符串1: " << s1 << endl;
    cout << "字符串2: " << s2 << endl;
    cout << "最长公共子序列长度: " << longestCommonSubsequence(s1, s2) << endl << endl;
    
    // 测试应用3：Floyd-Warshall最短路径
    cout << "=== 应用3：Floyd-Warshall最短路径 ===" << endl;
    const int INF = INT_MAX;
    vector<vector<int>> graph = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };
    vector<vector<int>> dist;
    floydWarshall(graph, dist);
    cout << "所有顶点对之间的最短路径:" << endl;
    for (int i = 0; i < dist.size(); ++i) {
        for (int j = 0; j < dist.size(); ++j) {
            if (dist[j] == INF) cout << "INF ";
            else cout << dist[j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    
    // 测试应用4：最大子数组和
    cout << "=== 应用4：最大子数组和 ===" << endl;
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "数组: ";
    for (int num : nums) cout << num << " ";
    cout << endl;
    cout << "最大子数组和: " << maxSubarraySum(nums) << endl << endl;
    
    // 测试应用5：爬楼梯
    cout << "=== 应用5：爬楼梯问题 ===" << endl;
    int n = 5;
    cout << "楼梯阶数: " << n << endl;
    cout << "不同的爬法数量: " << climbStairs(n) << endl;
    
    return 0;
}