概述
- 动态规划（
Dynamic Programming，简称DP）是一种通过分解问题来解决复杂问题的算法技术，特别适用于具有最优子结构性质的问题，即问题的最优解可以由其子问题的最优解构建而成 - 动态规划的核心思想是将问题分解成更小的子问题，并保存这些子问题的解，避免重复计算，从而提高效率
概念
- 分治思想
- 将问题分解为相互重叠的子问题，通过解决子问题来构建原问题的解
- 适用问题
- 通常用于解决具有最优子结构和重叠子问题性质的问题
- 方法
- 通过递归和记忆化搜索（自顶向下）或迭代（自底向上）的方法来求解问题
步骤
- 定义子问题
- 将原问题分解成若干子问题，找到子问题与原问题之间的关系
- 确定状态
- 确定每个子问题的状态，并找到状态转移方程
- 建立递归关系
- 根据子问题的解，建立状态转移方程，即递归关系
- 初始化
- 确定边界条件或初始状态
- 填表计算
- 使用自底向上或自顶向下的方法，依次计算子问题的解并存储，直至求解原问题
动态规划优缺点
优点
- 避免重复计算：
- 通过存储子问题的解，避免了重复计算，提高了效率
- 最优解：
- 在满足最优子结构性质的问题上，可以保证找到全局最优解
缺点
- 空间复杂度高：
- 需要额外的存储空间来保存子问题的解
- 适用范围有限：
- 仅适用于具有最优子结构性质和重叠子问题性质的问题
常见动态规划问题
- 斐波那契数列：
- 计算斐波那契数列的第 n 项
- 背包问题：
- 在给定的重量限制下，选择物品使得总价值最大
- 最长公共子序列：
- 找到两个序列的最长公共子序列
- 编辑距离：
- 计算将一个字符串转换成另一个字符串所需的最少操作次数
- 最短路径问题：
- 在加权图中找到从一个节点到另一个节点的最短路径
- 矩阵链乘法：
- 确定矩阵相乘的最优顺序，以使乘法次数最少
斐波那契数列
递归方法（存在重叠子问题）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> using namespace std; int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } int main() { int n = 10; cout << "Fibonacci number is " << fib(n) << endl; return 0; } |
动态规划方法（避免重复计算）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> using namespace std; int fib(int n) { if (n <= 1) return n; 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 main() { int n = 10; cout << "Fibonacci number is " << fib(n) << endl; return 0; } |
0/1 背包问题
概述
- 给定一组物品，每个物品有重量和价值，在总重量不超过背包容量的前提下，选择物品使得总价值最大
动态规划解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #include <vector> using namespace std; int knapsack(int W, vector<int>& weights, vector<int>& values, int n) { vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= n; i++) { for (int w = 0; w <= W; w++) { if (weights[i - 1] <= w) dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]); else dp[i][w] = dp[i - 1][w]; } } return dp[n][W]; } int main() { int W = 50; // 背包容量 vector<int> weights = {10, 20, 30}; vector<int> values = {60, 100, 120}; int n = weights.size(); cout << "Maximum value in Knapsack = " << knapsack(W, weights, values, n) << endl; return 0; } |
最长公共子序列
概述
- 给定两个序列，找到它们的最长公共子序列
动态规划解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <vector> using namespace std; int lcs(string X, string Y) { int m = X.length(); int 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]; } int main() { string X = "AGGTAB"; string Y = "GXTXAYB"; cout << "Length of LCS is " << lcs(X, Y) << endl; return 0; } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
热评文章
- 排序_堆排序 0
- 贪心算法 0
- 数据结构_最小优先级队列 0
- 排序_快速排序 0
- 一些变量值交换的方法 0
- 匹配_KMP模式匹配算法：二 0