经典算法——动态规划

欢迎大家来到IT世界,在知识的湖畔探索吧!

动态规划（Dynamic Programming, DP）

动态规划是一种在数学、计算机科学和经济学中用于求解具有重叠子问题和最优子结构的问题的算法策略。它通过将原问题分解为相互关联的子问题，并存储这些子问题的解以避免重复计算，从而有效地找到最优化解决方案。

动态规划的基本步骤：

1. 定义状态：明确要解决的问题中涉及的状态变量。

2. 找出状态转移方程：描述如何从一个或多个较小子问题的解构建出更大规模子问题的解。

3. 初始化基础情况：确定递归过程中的起始点或基本情况，即没有更小子问题时的解。

4. 自底向上计算：通常使用数组或矩阵来存储每个子问题的解，从最简单的情况开始逐步计算到最终问题。

C++ 示例：斐波那契数列（经典动态规划问题）

斐波那契数列中，F(n)是前两个数之和，即F(n) = F(n-1) + F(n-2)，且F(0)=0, F(1)=1。

#include <iostream> #include <vector> // 使用动态规划计算第n个斐波那契数 int fibonacci(int n) { // 初始化动态规划数组 std::vector<int> dp(n + 1, 0); // 基础情况 dp[0] = 0; if (n >= 1) dp[1] = 1; // 自底向上计算每个斐波那契数 for (int i = 2; i <= n; ++i) { dp[i] = dp[i - 1] + dp[i - 2]; } // 返回第n个斐波那契数 return dp[n]; } int main() { int n = 10; std::cout << "The " << n << "th Fibonacci number is: " << fibonacci(n) << "\n"; return 0; }

欢迎大家来到IT世界,在知识的湖畔探索吧!

更复杂的动态规划示例：最长公共子序列（LCS）

给定两个字符串A和B，寻找它们的最长公共子序列。

欢迎大家来到IT世界,在知识的湖畔探索吧!#include <iostream> #include <string> #include <vector> using namespace std; // 定义二维DP表 vector<vector<int>> lcs_table; // 计算两个字符串的最长公共子序列长度 void lcsLength(string a, string b, int m, int n) { // 初始化dp表 lcs_table.resize(m + 1, vector<int>(n + 1, 0)); // 自底向上填充dp表 for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (a[i - 1] == b[j - 1]) { lcs_table[i][j] = lcs_table[i - 1][j - 1] + 1; } else { lcs_table[i][j] = max(lcs_table[i - 1][j], lcs_table[i][j - 1]); } } } } // 重建最长公共子序列 string buildLCS(int m, int n) { string lcs = ""; int i = m, j = n; while (i > 0 && j > 0) { if (a[i - 1] == b[j - 1]) { lcs.push_back(a[i - 1]); i--; j--; } else if (lcs_table[i - 1][j] > lcs_table[i][j - 1]) { i--; } else { j--; } } reverse(lcs.begin(), lcs.end()); // 反转字符串得到正确顺序的LCS return lcs; } int main() { string str1 = "ABCBDAB", str2 = "BDCAB"; int m = str1.size(); int n = str2.size(); // 计算LCS长度 lcsLength(str1, str2, m, n); // 重建并打印最长公共子序列 cout << "Longest Common Subsequence is: " << buildLCS(m, n) << endl; return 0; }

以上代码首先定义了一个二维动态规划表lcs_table，用来存储子问题的解。然后根据当前字符是否相等，更新表格中的值。最后，通过回溯lcs_table来重构最长公共子序列。