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

算法入门--动态规划（C++）

news 2025/7/14 5:26:21

深入浅出掌握动态规划核心思想，图文并茂+实战代码

什么是动态规划？

动态规划（Dynamic Programming, DP）是一种高效解决多阶段决策问题的方法。它通过将复杂问题分解为重叠子问题，并存储子问题的解（避免重复计算），最终解决原问题。

动态规划适用场景

重叠子问题：问题可分解为重复出现的子问题
最优子结构：问题的最优解包含子问题的最优解
无后效性：当前状态一旦确定，后续决策不受之前决策影响

一、从斐波那契数列入门（记忆化搜索）

斐波那契数列是理解DP思想的完美起点：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

1.1 递归解法（低效）

int fib(int n) {if (n <= 1) return n;return fib(n-1) + fib(n-2);
}

问题：存在大量重复计算，时间复杂度O(2^n)

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

#include <vector>
using namespace std;int fibMemo(int n, vector<int>& memo) {if (n <= 1) return n;if (memo[n] != -1) return memo[n]; // 已计算过memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);return memo[n];
}int fib(int n) {vector<int> memo(n+1, -1); // 初始化记忆数组return fibMemo(n, memo);
}

优点：时间复杂度降为O(n)，空间复杂度O(n)

二、数塔问题（经典DP）

问题描述：从塔顶到塔底，每次只能向下或右下移动，求最大路径和。

        5/ \8   3/ \ / \12  7  16/ \ / \ / \4   10  11  6

2.1 DP解法思路

状态定义：dp[i][j]表示从第i行第j列出发到底部的最大路径和
状态转移：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])
边界条件：最底层dp值等于元素本身

2.2 C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int maxPathSum(vector<vector<int>>& tower) {int n = tower.size();vector<vector<int>> dp(n, vector<int>(n, 0));// 初始化最后一行for (int j = 0; j < n; ++j) dp[n-1][j] = tower[n-1][j];// 自底向上计算for (int i = n-2; i >= 0; --i) {for (int j = 0; j <= i; ++j) {dp[i][j] = tower[i][j] + max(dp[i+1][j], dp[i+1][j+1]);}}return dp[0][0];
}int main() {vector<vector<int>> tower = {{5},{8, 3},{12, 7, 16},{4, 10, 11, 6}};cout << "最大路径和: " << maxPathSum(tower) << endl; // 输出: 5+8+7+11=31return 0;
}

三、最长上升子序列（LIS）

问题描述：给定数组，找到最长严格递增子序列的长度示例：[10,9,2,5,3,7,101,18] -> 最长上升子序列[2,5,7,101]长度为4

3.1 DP解法

状态定义：dp[i]表示以nums[i]结尾的LIS长度
状态转移：
结果：max(dp[0...n-1])

3.2 C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;vector<int> dp(nums.size(), 1);int maxLen = 1;for (int i = 1; i < nums.size(); ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1);}}maxLen = max(maxLen, dp[i]);}return maxLen;
}int main() {vector<int> nums = {10,9,2,5,3,7,101,18};cout << "最长上升子序列长度: " << lengthOfLIS(nums) << endl; // 输出4return 0;
}

时间复杂度：O(n²) 优化：二分查找可优化至O(nlogn)

四、0-1背包问题（经典DP）

问题描述：给定n件物品（重量w[i], 价值v[i]）和容量为C的背包，如何装包使总价值最大？

4.1 DP解法思路

状态定义：dp[i][j]表示前i件物品放入容量为j的背包的最大价值
状态转移：

4.2 C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int knapsack(int C, vector<int>& w, vector<int>& v) {int n = w.size();vector<vector<int>> dp(n+1, vector<int>(C+1, 0));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= C; ++j) {if (j < w[i-1]) {  // 注意下标偏移dp[i][j] = dp[i-1][j];} else {dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j - w[i-1]]);}}}return dp[n][C];
}int main() {vector<int> weights = {2, 3, 4, 5};  // 物品重量vector<int> values = {3, 4, 5, 6};   // 物品价值int capacity = 8;                    // 背包容量cout << "最大价值: " << knapsack(capacity, weights, values) << endl; // 输出: 10 (选3+5+6)return 0;
}

五、动态规划解题步骤总结

定义状态：明确dp数组的含义
确定转移方程：关键步骤，找出状态间关系
初始化：设置边界值
确定计算顺序：自底向上或自顶向下
输出结果：从最终状态获取答案
空间优化：滚动数组等技巧（可选）

六、常见DP模型

问题类型	典型问题	状态转移特征
线性DP	最长上升子序列	沿数组顺序转移
区间DP	矩阵链乘法、石子合并	从小区间向大区间转移
背包问题	0-1背包、完全背包	物品选择决策
树形DP	二叉树最大路径和	在树结构上递归转移
状态压缩DP	旅行商问题(TSP)	用二进制表示状态