#创作计划#动态规划【C++优质版】

Ysjt | 深 ™

2024-12-02 11:23:46

发布于：广东

26阅读

0回复

0点赞

（本文未经作者书面允许，禁止以任何形式传播（包括但不限于转载，翻译……）如需引用请标注原作者）

Intro：

动态规划是一种用于解决优化问题的算法策略。在 C++ 中，它主要用于处理那些具有重叠子问题和最优子结构性质的问题。那么应该如何解决动态规划内容呢？？？

01 动态规划的基本概念：

动态规划的概念最早是由美国数学家理查德・贝尔曼（Richard Bellman）在 20 世纪 50 年代开发的。当时，他在研究多阶段决策过程的优化问题时提出了这个方法。这个方法最初是为了解决诸如资源分配、生产计划和控制系统等实际问题。

名称的由来也很有意思，“动态规划” 这个名字中的 “动态” 是指问题是随时间或阶段动态变化的，而 “规划” 则强调了寻找最优策略的过程。贝尔曼的工作为后来许多复杂的优化问题提供了一种系统性的解决方法，并且在计算机科学、经济学、工程学等众多领域得到了广泛的应用。

02：动态规划性质：

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

03：特点

最优子结构：问题的最优解可以由子问题的最优解组合而成。
子问题重叠：在求解过程中，会多次遇到相同的子问题。
无后效性：一旦某个阶段的状态确定，就不受后续阶段决策的影

那么现在问题来了！！！！我们应该如何解决动态规划的这一类问题呢？？？如果你看到这了！心目中还并没有一个答案！！！那么就请你接着往下看吧！

04：动态规划求解步骤：

1.确定问题的状态
状态是描述问题在某一阶段的特征，通常用一个或多个变量来表示。
例如，在求解最长上升子序列问题中，可以用一个数组来表示当前的状态，数组中的每个元素表示以该位置的元素结尾的最长上升子序列的长度。
2.确定状态转移方程
状态转移方程是描述不同状态之间如何转移的数学表达式。
例如，在背包问题中，状态转移方程可以表示为：

$dp[i][j]=max（dp[i-1],dp[i-1][j-w[i]]+v[i]）$

，其中表示前个物品放入容量为的背包中所能获得的最大价值，表示第个物品的重量，表示第个物品的价值。
3.确定初始状态
初始状态是问题的最基本情况，可以通过直接计算得到。
例如，在斐波那契数列问题中，初始状态为， $dp[0]=0,dp[1]=1$ 。
4.确定计算顺序
根据问题的特点和状态转移方程，确定计算状态的顺序。
通常可以采用自底向上或自顶向下的方式进行计算。

05:C++求解动态规划步骤：

最长上升子序列问题
问题描述：给定一个整数数组，求其中最长上升子序列的长度。
代码实现：

#include <iostream>
#include <vector>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

背包问题
问题描述：有一个容量为的背包和种物品，每种物品有重量和价值，求在不超过背包容量的情况下，能够装入背包的最大价值。
代码实现：

#include <iostream>
#include <vector>

using namespace std;

int knapsack(int V, vector<int>& w, vector<int>& v) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (j < w[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
        }
    }
    return dp[n][V];
}

（注：本代码由豆包AI智能提供）

06：空间规划的优化：

1.空间优化
在一些情况下，可以通过优化状态的表示和计算顺序，减少动态规划所需的空间。
例如，在背包问题中，可以使用一维数组来代替二维数组，从而减少空间复杂度。
2.时间优化
可以通过使用更高效的数据结构或算法来优化动态规划的时间复杂度。
例如，在一些问题中，可以使用线段树或树状数组来加速状态的计算。