L6_04 简单动态规划

一、动态规划概述

1.1 动态规划的定义

动态规划（Dynamic Programming，DP）是一种将复杂问题分解为子问题求解的算法思想。

1.2 动态规划的特点

• 最优子结构：问题的最优解包含子问题的最优解
• 重叠子问题：子问题会被重复计算
• 状态转移：通过状态转移方程求解

1.3 动态规划的步骤

1. 定义状态
2. 确定状态转移方程
3. 初始化边界条件
4. 计算最优解

二、一维动态规划

2.1 斐波那契数列

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

2.2 爬楼梯问题

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev1 = 1, prev2 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev1 = prev2;
        prev2 = curr;
    }
    return prev2;
}

2.3 最大子数组和

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

三、简单背包问题

3.1 0-1背包问题

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];
}

3.2 完全背包问题

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

3.3 背包问题对比

类型	物品选择	内层循环方向
0-1背包	每种物品选或不选	逆序
完全背包	每种物品可选多次	顺序

四、其他一维DP问题

4.1 最长递增子序列

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

4.2 最长回文子串

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    int start = 0, max_len = 1;
    
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2 || dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (len > max_len) {
                        max_len = len;
                        start = i;
                    }
                }
            }
        }
    }
    return s.substr(start, max_len);
}

4.3 编辑距离

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    
    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];
}

五、动态规划优化技巧

5.1 空间优化

• 使用滚动数组
• 只保留必要的状态

5.2 时间优化

• 使用二分查找优化
• 使用单调队列优化

5.3 常见优化策略

问题类型	优化方法
一维DP	滚动数组
LIS	二分查找
区间DP	枚举长度
树形DP	记忆化搜索