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

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

什么是动态规划？

动态规划（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 using namespace std;int fibMemo(int n, vector& 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 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解法思路

1. 状态定义：dp[i][j]表示从第i行第j列出发到底部的最大路径和

2. 状态转移：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])

3. 边界条件：最底层dp值等于元素本身

2.2 C++实现

#include #include #include using namespace std;int maxPathSum(vector<vector>& tower) { int n = tower.size(); vector<vector> dp(n, vector(n, 0)); // 初始化最后一行 for (int j = 0; j = 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> tower = { {5}, {8, 3}, {12, 7, 16}, {4, 10, 11, 6} }; cout << \"最大路径和: \" << maxPathSum(tower) << endl; // 输出: 5+8+7+11=31 return 0;}

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

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

3.1 DP解法

1. 状态定义：dp[i]表示以nums[i]结尾的LIS长度

2. 状态转移：

3. 结果：max(dp[0...n-1])

3.2 C++实现

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

#include #include #include using namespace std;int knapsack(int C, vector& w, vector& v) { int n = w.size(); vector<vector> dp(n+1, vector(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 weights = {2, 3, 4, 5}; // 物品重量 vector values = {3, 4, 5, 6}; // 物品价值 int capacity = 8;  // 背包容量 cout << \"最大价值: \" << knapsack(capacity, weights, values) << endl; // 输出: 10 (选3+5+6) return 0;}