动态规划算法（Dynamic Programming）

一、算法核心原理

1.1 基本思想

动态规划是一种将复杂问题分解为简单子问题的算法设计范式。与分治法不同，动态规划解决的问题通常具有重叠子问题和最优子结构的特性。

1.2 核心要素

1.最优子结构：问题的最优解包含子问题的最优解
2.重叠子问题：递归求解时会重复计算相同的子问题。
3.状态转移：如何从较小的子问题推导出较大问题的解。

二、算法步骤

2.1 四步法

1.定义状态
2.确定状态转移方程
3.设置初始条件
4.确定计算顺序
5.返回最终结果

三、实现方式对比

3.1自顶向下（记忆化搜索）

优点：思路直观，类似递归
缺点：递归开销，可能栈溢出

3.2 自底向上（递推）

优点：高效，无递归开销
缺点：需要明确计算顺序

四、经典问题实现

4.1 斐波那契数列

问题描述：计算第n个斐波那契数

#include <iostream>
#include <vector>
using namespace std;
//方法1 ：朴素递归（时间复杂度高，不推荐）
int fib_recursive(int n ){
  if(n<=1) return n;
  return fib_recursive(n-1)*fib_recursive(n-2);
}

//方法2：自顶向下记忆化搜索
int fib_memo(int n,vector<int>&memo){
 if(n<=1) return n;
 if(memo[n] != -1) return memo[n];
 memo[n] = fib_meo(n-1,memo)+fib_memo(n-2,memo);
 return memo[n];
}
int fib_top_down(int n){
  vector<int> memo(n+1,-1);
  return fib_memo(n,memo);
}

//方法3：自底向上递推
int fib_bottom_up(int n){
  if(n<=1) return n;
  vector<int> dp(n+1,0);
  dp[0] = 0;
  dp[1] = 1;
  for(int i=2;i<=n;i++){
    dp[i]=dp[i-1]+dp[i-2];
  }
  return dp[n];
}

//方法4：空间优化版本
int fib_optimized(int n){
 if(n<=1) return n;
 int prev2 = 0; //dp[i-2];
 int prev1 = 1; //dp[i-1];
 int current; //dp[i];
  for(int i=2;i<=n;i++){
    current = prev1+prev2;
    prev2=prev1;
    prev1=current;
  }
  return current;
}

复杂度分析

• 朴素递归：时间复杂度O(2^n), 空间复杂度O（n）
• 记忆优化搜索：时间复杂度O(n),空间复杂度O(n)
• 自底向上：时间复杂度O(n),空间复杂度O(n)
• 优化版本：时间复杂度O(n),空间复杂度O(1)

4.2 0-1背包问题

问题描述：从n个物品中选择，每个物品有重量和价值，背包容量有限，求最大价值。

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

//方法一：基础二维DP
int knapsack_2d(int W,vector<int>&wt,vector<int>&val,int n){
 //d[i][w] 表示考虑前i个物品，容量为w时的最大价值
 vector<vector<int>>dp(n+1,vector<int>(W+1,0));
 for(int i=1; i<=n;i++){
   for (int w=i;w<=W; w++){
        //不选第i个物品
        dp[i][w]=dp[i-1][w];
        //如果能放得下，考虑选第i个物品
        if(w>=wt[i-1]){
           dp[i][w] = max(dp[i][w],dp[i-1][w-wt[i-1]]+val[i-1]);
        }
    }
 }
}
//方法二：一维DP优化（滚动数组）
int knapsack_1d(int W,vector<int>&wt,vector<int>&val,int n){
   vector<int>dp(W+1,0);
   for(int i=0; i<n; i++){
    //必须倒序遍历，保证每个物品只被计算一次
    for(int w=W;w>=wt[i];w--){
      dp[w] = max(dp[w],dp[w-wt[i]]+val[i]);
      }
    }
    return dp[W];
}

//方法三:带路径记录
void knapsack_with_path(int W, vector<int>& wt, vector<int>& val, int n) {
    //d[i][w] 表示考虑前i个物品，容量为w时的最大价值
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    
    // 填充DP表
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (w >= wt[i-1]) {
                dp[i][w] = max(dp[i-1][w], 
                              dp[i-1][w - wt[i-1]] + val[i-1]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    // 回溯找选择的物品
    cout << "最大价值: " << dp[n][W] << endl;
    cout << "选择的物品: ";
    
    int w = W;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            cout << i << " ";  // 选择第i个物品
            w -= wt[i-1];
        }
    }
    cout << endl;
}

复杂度分析

• 时间复杂度：O(n+W),其中n为物品数，W为背包容量
• 空间复杂度：二维O(n*w), 一维O(W)

4.3最长公共子序列

问题描述：求两个序列的最长公共子序列长度

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int longestCommSubSequence(string text1,string text2){
  int m = text1.length();
  int n = text2.length();
  //dp[i][j] 表示text1[0....i-1]和tex2[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(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];
}
//空间优化版本
int longestCommSubSequence_opt(string text1,string text2){
  int m = text1.length();
  int n = text2.length();
  if(m<n){
     swap(text1,text2);
     swap(m,n);
  }
  vector<vector<int>> dp(2,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%2][j] =dp[(i-1)%2][j-1]+1;
      }else{
        dp[i%2][j] = max(dp[(i-1)%2][j],dp[i%2][j-1]);
      }
    }
}
return dp[m%2][n];
}  

复杂度分析

• 时间复杂度：O（m*n）
• 空间复杂度：优化前O(m*n) ,优化后O(min(m,n))

五、 复杂度总结：

5.1 时间复杂度

动态规划的时间复杂度通常由以下因素决定：

• 状态数量：通常是多维度的乘积
• 状态转移复杂度：每个状态计算需要的操作数
• 计算顺序：确保子问题已经求解
• 一般公式：时间复杂度=状态数量*单个状态转移复杂度

5.2空间复杂度优化技巧

1.滚动数组

// 二维降一维
vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++) {
    for (int w = W; w >= wt[i]; w--) {  // 注意遍历顺序
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    }
}

2.状态压缩（适用于状态较少的情况）

int dp[1<<n][n];  // 用二进制位表示城市访问状态

3.降维技巧

// 如果当前状态只依赖前一行/前一列
// 可以使用两个一维数组交替
vector<int> prev(W+1, 0), curr(W+1, 0);
for (int i = 0; i < n; i++) {
    swap(prev, curr);
    for (int w = 0; w <= W; w++) {
        // 计算curr[w]
    }
}

六、模版代码

class DPSolution {
public:
    // 通用框架
    int solveDP(int n, int m) {
        // 1. 定义状态
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        
        // 2. 初始化
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int j = 0; j <= m; j++) dp[0][j] = 1;
        
        // 3. 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 状态转移方程
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        // 4. 返回结果
        return dp[n][m];
    }
};