动态规划基本操作

动态规划基本操作详解（C++）

线性动态规划戳这里
区间动态规划戳这里
状态压缩动态规划戳这里
树状动态规划戳这里
数位动态规划戳这里
树状数组动态规划戳这里

动态规划（Dynamic Programming）是一种通过将复杂问题分解为重叠子问题并存储子问题解来优化求解的方法。以下是核心概念和C++实现示例：

核心思想

1. 重叠子问题：问题可分解为重复计算的子问题
2. 最优子结构：问题最优解包含子问题最优解
3. 记忆化存储：避免重复计算，提升效率

基本操作步骤

1. 定义状态：用数组表示问题状态
2. 状态转移方程：描述状态间关系
3. 初始化：设置边界条件
4. 计算顺序：确定状态计算方向
5. 空间优化（可选）：减少存储使用

经典问题示例（C++实现）

1. 斐波那契数列

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

int fib(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];
}
// 空间优化版
int fib_optimized(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

2. 零一背包问题

int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.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 (wt[i-1] > w) {
                dp[i][w] = dp[i-1][w];
            } else {
                dp[i][w] = max(dp[i-1][w], 
                              val[i-1] + dp[i-1][w - wt[i-1]]);
            }
        }
    }
    return dp[n][W];
}

3. 最长公共子序列（LCS）

int lcs(string X, string Y) {
    int m = X.length(), n = Y.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 (X[i-1] == Y[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];
}

4. 矩阵链乘法

int matrixChain(vector<int>& p) {
    int n = p.size()-1;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] 
                          + p[i]*p[k+1]*p[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

动态规划类型

优化技巧

1. 滚动数组：减少空间复杂度

   // 斐波那契滚动数组示例
   int fib(int n) {
       if (n < 2) return n;
       int a = 0, b = 1;
       for (int i = 2; i <= n; i++) {
           int t = b;
           b = a + b;
           a = t;
       }
       return b;
   }
   

2. 记忆化搜索：自顶向下递归+缓存

   vector<int> memo;
   int fib_memo(int n) {
       if (n <= 1) return n;
       if (memo[n] != -1) return memo[n];
       return memo[n] = fib_memo(n-1) + fib_memo(n-2);
   }
   

3. 状态压缩：使用位运算减少维度

解题模板

int dp_solution(/* 输入参数 */) {
    // 1. 初始化DP数组
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    // 2. 设置边界条件
    for (int i = 0; i < m; i++) dp[i][0] = ...;
    for (int j = 0; j < n; j++) dp[0][j] = ...;
    
    // 3. 状态转移
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = ... // 状态转移方程
        }
    }
    
    // 4. 返回结果
    return dp[m-1][n-1];
}

掌握动态规划需要理解"状态定义"和"状态转移"两个核心概念，通过练习经典问题培养解题直觉。