动态规划

动态规划核心概念

是一种通过将复杂问题分解为重叠子问题，并存储子问题的解来避免重复计算，从而优化时间复杂度的算法思想。
核心要素
状态定义：确定dp[i]（或多维dp[i][j]）代表什么含义（这是 DP 的核心）。
状态转移方程：找到dp[i]与子问题dp[i-1], dp[i-2]…的关系（最关键的一步）。
初始条件：确定边界情况的解（如dp[0], dp[1]）。=
结果获取：最终答案对应哪个dp值。
适用场景
问题具有重叠子问题（如斐波那契数列，计算f(5)需要f(4)和f(3)，计算f(4)又需要f(3)和f(2)）。
问题具有最优子结构（最优解可以通过子问题的最优解推导出来）。

两种实现方式

1.自顶向下（记忆化搜索）

#include <vector>
#include <unordered_map>
#include <functional>
using namespace std;

// 示例：斐波那契数列
int fib_memo(int n, vector<int>& memo) {
   if (n <= 1) return n;
   if (memo[n] != -1) return memo[n]; // 已计算过
   memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
   return memo[n];
}

// 使用lambda和function实现通用记忆化
template<typename ReturnType, typename... Args>
function<ReturnType(Args...)> memoize(function<ReturnType(Args...)> func) {
   unordered_map<tuple<Args...>, ReturnType> cache;
   return [=](Args... args) mutable {
       auto key = make_tuple(args...);
       if (cache.find(key) == cache.end()) {
           cache[key] = func(args...);
       }
       return cache[key];
   };
}

2.自底向上（迭代法）

// 斐波那契数列迭代版
int fib_dp(int n) {
    if (n <= 1) return n;
    
    // 方法1：使用vector存储所有状态
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
    
    // 方法2：空间优化（滚动数组）
    // int prev = 0, curr = 1;
    // for (int i = 2; i <= n; i++) {
    //     int next = prev + curr;
    //     prev = curr;
    //     curr = next;
    // }
    // return curr;
}

经典问题模板

1.线性DP：最长递增子序列

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    vector<int> dp(n, 1); // dp[i]: 以nums[i]结尾的LIS长度
    int maxLen = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// O(nlogn)优化版（贪心+二分）
int lengthOfLIS_optimized(vector<int>& nums) {
    vector<int> tails; // tails[i]: 长度为i+1的LIS的最小末尾值
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

2.0-1背包问题

int knapSack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(
                    dp[i-1][w],  // 不选第i个物品
                    dp[i-1][w - weights[i-1]] + values[i-1]  // 选第i个物品
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

// 空间优化版（一维数组）
int knapSack_optimized(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 逆序遍历，确保每个物品只选一次
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

3.完全背包问题

int completeKnapSack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 正序遍历，允许重复选择
        for (int w = weights[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

4.最长公共子序列

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

5. 编辑距离

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

6.矩阵连乘最小代价

int matrixChainMultiplication(vector<int>& dims) {
    int n = dims.size() - 1;  // 矩阵个数
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // length表示矩阵链长度
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            dp[i][j] = INT_MAX;
            
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + 
                          dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

7.状态压缩DP：旅行商问题

int travelingSalesman(vector<vector<int>>& dist) {
    int n = dist.size();
    int m = 1 << n;
    vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
    dp[1][0] = 0;  // 从城市0出发
    
    for (int mask = 1; mask < m; mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], 
                                    dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    int minCost = INT_MAX;
    int fullMask = (1 << n) - 1;
    for (int u = 1; u < n; u++) {
        if (dist[u][0] != -1) {
            minCost = min(minCost, dp[fullMask][u] + dist[u][0]);
        }
    }
    return minCost;
}

动态规划解题框架

class DPSolver {
public:
    // 框架方法
    int solveDP(vector<int>& nums) {
        int n = nums.size();
        
        // 1. 定义状态数组
        vector<int> dp(n, 0);  // 一维DP
        // vector<vector<int>> dp(n, vector<int>(n, 0));  // 二维DP
        
        // 2. 初始化
        dp[0] = nums[0];
        
        // 3. 状态转移
        for (int i = 1; i < n; i++) {
            // 根据问题定义状态转移方程
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        // 4. 返回结果
        return dp[n-1];
    }
    
    // 通用打印DP表函数（调试用）
    template<typename T>
    void printDPTable(const vector<vector<T>>& dp) {
        for (const auto& row : dp) {
            for (const auto& val : row) {
                cout << val << "\t";
            }
            cout << endl;
        }
    }
};

空间优化技巧

滚动数组

// 斐波那契滚动数组
int fib_rolling(int n) {
    if (n <= 1) return n;
    
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// 二维DP空间优化（如背包问题）
int knapSack_2d_optimized(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(2, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        int curr = i % 2;
        int prev = 1 - curr;
        
        for (int w = 0; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[curr][w] = max(dp[prev][w], 
                                 dp[prev][w - weights[i-1]] + values[i-1]);
            } else {
                dp[curr][w] = dp[prev][w];
            }
        }
    }
    return dp[n % 2][W];
}

常见优化技巧

单调队列优化

// 滑动窗口最大值（可用于某些DP优化）
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;
    vector<int> result;
    
    for (int i = 0; i < nums.size(); i++) {
        // 移除不在窗口内的元素
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }
        
        // 维护单调递减队列
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

实用调试技巧

#include <iostream>
#include <iomanip>

// 调试宏
#define DEBUG_DP 1

#if DEBUG_DP
    #define DP_LOG(msg, ...) printf("[DP] " msg "\n", ##__VA_ARGS__)
    #define PRINT_DP_TABLE(dp) \
        do { \
            cout << "DP Table:" << endl; \
            for (const auto& row : dp) { \
                for (int val : row) { \
                    cout << setw(4) << val << " "; \
                } \
                cout << endl; \
            } \
        } while(0)
#else
    #define DP_LOG(msg, ...)
    #define PRINT_DP_TABLE(dp)
#endif

// 带调试的DP示例
int debugDPExample(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 0);
    
    DP_LOG("开始计算，n = %d", n);
    
    // 初始化
    dp[0] = nums[0];
    if (n > 1) dp[1] = max(nums[0], nums[1]);
    
    // 状态转移
    for (int i = 2; i < n; i++) {
        DP_LOG("计算 dp[%d]", i);
        dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        DP_LOG("dp[%d] = max(%d, %d + %d) = %d", 
              i, dp[i-1], dp[i-2], nums[i], dp[i]);
    }
    
    return dp[n-1];
}

重要注意事项

数组边界：注意dp数组大小，通常需要n+1
初始化：不要忘记初始条件
遍历顺序：确保依赖的状态已计算
空间优化：注意逆序/正序遍历的区别

总结

数据类型：使用long long防止溢出
动态规划的核心是状态定义 + 状态转移方程，先明确dp数组的含义，再推导子问题间的关系。
实现时优先保证逻辑正确，再考虑空间优化（如用变量代替数组）。
一维 DP 适用于单维度依赖的问题（如斐波那契、LIS），二维 DP 适用于二维网格 / 双维度依赖的问题（如不同路径、最长公共子序列）。