文章目录
- 介绍
- 解题步骤
- 题型
- 背包问题
- 01背包问题
- 朴素算法（递归实现）
- 备忘录算法(记忆化搜索)
- 递推求解算法（动态规划）
- 连续子段和问题
- 最大连续子序列和
- 最大连续子序列和的最优方案
- 递推问题
- 斐波那契数列II
- 数塔II
- 上楼II
- 最长不下降子序列问题
- 最长上升子序列
介绍
动态规划通常用于求解最优解问题，动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题会被重复计算多次。而动态规划的做法是将已解决子问题的答案保存下来，在需要子问题答案的时候便可直接获得，而不需要重复计算，这样就可以避免大量的重复计算，提高效率。
解题步骤
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
题型
背包问题
01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
朴素算法（递归实现）
这个问题是一个组合优化问题，其中目标是在不超过背包容量的前提下，从一组物品中选择一些物品，使得这些物品的总价值最大。
递归逻辑如下：
- 基本情况：如果背包容量
C为0或物品数量n为0，返回0，因为没有物品可以放入背包或没有剩余空间。 - 如果最后一个物品的重量
weights[n - 1]大于背包的剩余容量C，则不考虑这个物品，递归调用Recursive函数，减少物品数量n。 - 否则，考虑两种情况：
- 不选择最后一个物品，继续递归调用
Recursive函数。 - 选择最后一个物品，将其价值加到递归调用
Recursive函数的结果上，但需要从背包容量中减去这个物品的重量。
- 不选择最后一个物品，继续递归调用
// 递归算法
int Recursive(int C, int weights[], int values[], int n) {
if (n == 0 || C == 0) {
return 0;
}
if (weights[n - 1] > C) {
return Recursive(C, weights, values, n - 1);
}
else {
return max(Recursive(C, weights, values, n - 1),
values[n - 1] + Recursive(C - weights[n - 1], weights, values, n - 1));
}
}
备忘录算法(记忆化搜索)
备忘录技术（Memoization）的核心思想是存储已经计算过的结果，以避免在递归过程中对同一子问题的多次计算。当递归函数遇到一个之前已经计算过的子问题时，它可以直接从备忘录中获取结果，而不需要重新计算。这样做可以显著减少计算量，提高算法的效率。
memo[n][C] 代表在考虑前 n 个物品且背包容量为 C 时的最大价值。如果 memo[n][C] 已经被赋值（不是 -1），这意味着：
- 这个问题之前已经被计算过。
- 它的值是正确的，因为递归过程中会正确地计算并存储每个子问题的最大价值。
由于背包问题是一个优化问题，每次计算得到的 memo[n][C] 是在当前条件下能够得到的最大价值，这个值是最优解，不会因为再次计算而改变。因此，一旦 memo[n][C] 被计算并存储，它的值就是最终答案，不需要再次更新。
直接返回已经计算过的值有以下几个原因：
- 避免重复计算：如果再次计算，会浪费计算资源，尤其是对于大型问题，这种重复计算会导致效率极低。
- 保持最优性：每次递归调用都会找到在当前条件下的最大价值，因此存储的值是最优的，没有必要更新。
- 确保正确性：递归算法保证了每个子问题只被计算一次，并且其结果被正确地存储和使用。
简而言之，备忘录中的值一旦被计算并存储，就代表了在给定子问题条件下的最优解，因此不需要再次计算或更新。这就是为什么在备忘录算法中，如果发现某个值已经被计算过，就直接返回该值，而不是重新计算或更新它。
备忘录逻辑如下：
- 基本情况：如果物品数量
n为0或背包容量C为0，返回0。 - 查看备忘录：如果
memo[n][C]已经被计算过（不是-1），则直接返回其值。 - 如果最后一个物品的重量
weights[n - 1]大于背包的剩余容量C，则不考虑这个物品，递归调用Memoization函数。 - 否则，考虑两种情况：
- 不选择最后一个物品，递归调用
Memoization函数。 - 选择最后一个物品，将其价值加到递归调用
Memoization函数的结果上，但需要从背包容量中减去这个物品的重量。
- 不选择最后一个物品，递归调用
- 将计算结果存储到备忘录
memo[n][C]中，然后返回这个结果。
// 备忘录算法
int Memoization(int C, int weights[], int values[], int n, vector<vector<int>>& memo) {
if (n == 0 || C == 0) {
return 0;
}
if (memo[n][C] != -1) {
return memo[n][C];
}
int result;
if (weights[n - 1] > C) {
result = Memoization(C, weights, values, n - 1, memo);
}
else {
result = max(Memoization(C, weights, values, n - 1, memo),
values[n - 1] + Memoization(C - weights[n - 1], weights, values, n - 1, memo));
}
memo[n][C] = result; // 存储结果到备忘录
return result;
}
递推求解算法（动态规划）
动态规划是一种通过将复杂问题分解成更简单的子问题来解决的方法，并且通过存储这些子问题的解来避免重复计算。
算法步骤如下：
-
内存分配：使用
malloc为动态规划表V分配内存。V[i][j]表示考虑前i个物品且背包容量为j时的最大价值。 -
初始化边界条件：
- 如果背包容量为0，无论考虑多少物品，最大价值都是0，因此
V[i][0] = 0。 - 如果没有物品，无论背包容量多大，最大价值也是0，因此
V[0][j] = 0。
- 如果背包容量为0，无论考虑多少物品，最大价值都是0，因此
-
动态规划计算：
- 外层循环
i从1到n，表示考虑的物品数量。 - 内层循环
j从1到C，表示背包容量。 - 如果当前物品的重量大于背包容量，则不能放入背包，当前状态的最大价值等于不包含当前物品时的最大价值，即
V[i - 1][j]。 - 否则，考虑两种情况：不放入当前物品或放入当前物品。选择两者中价值更大的一个作为当前状态的最大价值。
- 外层循环
-
返回最大价值：计算完成后，
V[n][C]存储了最终的最大价值。 -
内存释放：使用
free释放之前分配的内存。
// 动态规划算法
int Dynamic(int C, int weights[], int values[], int n) {
int** V = (int**)malloc((n + 1) * sizeof(int*));
for (int i = 0; i <= n; i++) {
V[i] = (int*)malloc((C + 1) * sizeof(int));
}
// 初始化边界条件
for (int i = 0; i <= n; i++) {
V[i][0] = 0;
}
for (int j = 0; j <= C; j++) {
V[0][j] = 0;
}
// 动态规划计算最大价值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= C; j++) {
if (weights[i - 1] > j) {
V[i][j] = V[i - 1][j];
} else {
V[i][j] = max(V[i - 1][j], values[i - 1] + V[i - 1][j - weights[i - 1]]);
}
}
}
int max_value = V[n][C];
// 释放动态分配的内存
for (int i = 0; i <= n; i++) {
free(V[i]);
}
free(V);
return max_value;
}
连续子段和问题
最大连续子序列和
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int dp[N] = {0},a[N],n;
int main(){
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++){
dp[i] = max(dp[i-1]+a[i],a[i]);
}
cout << *max_element(dp+1,dp+n+1);
return 0;
}
最大连续子序列和的最优方案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int dp[N] = {0},start[N],a[N],n,terminal,maxRes = INT32_MIN;
int main(){
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
a[0] = 1;
for(int i=1;i<=n;i++){
if((a[i]+dp[i-1]) >= a[i]){
dp[i] = a[i]+dp[i-1];
start[i] = start[i-1];
}else{
dp[i] = a[i];
start[i] = i;
}
}
for(int i=1;i<=n;i++){
if(dp[i] > maxRes){
terminal = i;
maxRes = dp[i];
}
}
cout << maxRes << " " << start[terminal] << " " << terminal;
return 0;
}
递推问题
斐波那契数列II
#include<bits/stdc++.h>
using namespace std;
int dp[10002];
int main(){
dp[1] = 1;
dp[2] = 1;
int n;
cin >> n;
for(int i = 3;i <= n;i ++){
dp[i] = (dp[i-1] + dp[i-2]);
}
cout << dp[n]%10007;
}
数塔II
#include<bits/stdc++.h>
using namespace std;
int dp[101][101],a[101][101];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin >> a[i][j];
}
}
for(int i=1;i<=n;i++){
dp[n][i] = a[n][i];
}
for(int i=n-1;i>0;i--){
for(int j=1;j<=i;j++){
dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + a[i][j];
}
}
cout << dp[1][1];
}
上楼II
#include<bits/stdc++.h>
using namespace std;
int dp[100001],n;
int main(){
dp[1] = 1;
dp[2] = 2;
cin >> n;
for(int i=3;i<=n;i++){
dp[i] = (dp[i-1] + dp[i-2])%10007;
}
cout << dp[n];
}
最长不下降子序列问题
最长上升子序列
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N],n,dp[N];
int main(){
cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
for(int i = 0;i < n;i ++){
dp[i] = 1;
for(int j=0;j<i;j++){
if(a[j]<=a[i] && dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
}
}
}
cout << *max_element(dp,dp+n);
return 0;
}
