当前位置：首页 > news >正文

动态规划基本操作

news 2025/7/13 13:50:26

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

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

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

核心思想

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

基本操作步骤

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

经典问题示例（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];
}

动态规划类型

类型	特点	经典问题
线性DP	状态线性排列	最大子数组和
区间DP	处理区间最优解	矩阵链乘、石子合并
状态压缩DP	用位运算表示状态	旅行商问题(TSP)
树形DP	在树结构上进行状态转移	二叉树中的最大路径和
数位DP	处理数字位相关问题	数字计数问题
数位DP	处理快速更改查询	快速更改查询问题

优化技巧

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

// 斐波那契滚动数组示例
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;
}

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

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

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

解题模板

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