动态规划第十二周也写了一部分，只不过忘记放上去了。
新的一年啦，看到这里砸个祝福：新年快乐，身体健康，考试顺利，心想事成！
2024/1/6 周六
蓝桥杯2012省赛 微生物增殖（简单）
【解题思路】
其实新出生半分钟吃一个是干扰项，实际上是一分钟吃一个
【参考代码】
#include <iostream>
using namespace std;
int main()
{
// 请在此输入您的代码
int x = 10, y = 90;
for(int time = 1 ; time <= 60 ; time++)
{
y -= x; //Y被x个x吃掉，一分钟吃一次
if(time % 2 == 0) //Y每隔2分钟分裂一次
y *= 2;
if(time % 3 == 0) //X每隔3分钟分裂一次
x *= 2;
}
cout << y;
return 0;
}【输出结果】
动态规划的思想
分为线性DP，状态压缩DP，数位DP，树形DP。
动态规划解题步骤
基本步骤分为以下四步
(1)转换成子问题。对于动态规划,最重要的是把一个大的问题划分成若干子问题,即进行问题降阶,通过逐级降阶将问题简化,从而实现问题的求解。
(2)转移方程,把问题方程化。
(3)按照实际逻辑设置边界情况和初始条件。
(4)确定计算顺序并求解。
动态规划与分治法最大的差别
适合于用动态规划法求解的问题, 经分解后得到的子问题往往不是互相孤立的
(即下一子问题的求解是建立在上一子问题的解的基础上而进行的进一步求解)。
经典实例
背包问题
01背包问题
题目链接
题目：有一个背包可以装一定重的物品,如何装物品才能使得背包的价值最大? 背包能装的重量是 10 斤，可以装的物品有以下几种：
矿泉水(重5斤,价值 10)
书(重3斤,价值5)
小吃(重4斤,价值 8)
水果(重4斤,价值 9)
相机(重2斤,价值6)
请问:携带哪些物品时价值最高?
【参考代码】：
#include <iostream>
using namespace std;
#include <iomanip> //用于setw函数
int main()
{
int n, m; //物品个数，背包总重量
int value[100][100];
int v[100], w[100];
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i]; //重量，价值
for (int j = 0; j <= m; j++)
value[0][j] = 0;
for (int i = 1; i <= n; i++)
{
value[i][0] = 0;
for (int j = 1; j <= m; j++)
{
value[i][j] = value[i - 1][j];
if (j >= w[i])
//状态转移方程
value[i][j] = max(value[i - 1][j], value[i - 1][j - w[i]] + v[i]);
}
}
cout << "01背包各状态转换表：" << endl;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
cout << setw(3) << value[i][j]; //隔3格输出
cout << endl;
}
cout << "背包能装的最大价值为：" << value[n][m];
}【运行结果】：
优化后的01背包：
#include <iostream>
using namespace std;
int f[1001], v[1001], w[1001];
int main()
{
int n, m; //物品个数，背包总重量
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i]; //体积，价值
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= v[i]; j--)
{
//状态转移方程
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m];
}
完全背包问题
题目链接
【参考代码】：
#include <iostream>
using namespace std;
int n, m, f[1001], v[1001], w[1001];
int main(){
cin >> n >> m;
for(int i=1; i <= n; i++)
{
cin >> v[i] >> w[i];
}
for(int i=1; i <= n; i++)
for(int j = v[i]; j <= m; j++)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m];
}
【输出结果】
多重背包
题目链接
参考代码：
#include <iostream>
using namespace std;
int n, m, f[1001], v[1001], w[1001], l[1001];
int main()
{
cin >> n >> m;
for(int i=1; i <= n; i++)
cin >> v[i] >> w[i] >> l[i];
for(int i=1; i <= n; i++)
for(int k=1; k <= l[i]; k++)
for(int j=m; j>= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
}
【输出结果】：
分组背包
题目链接
【参考代码】
此代码未通过100%题目测试点
#include <iostream>
#include <vector>
using namespace std;
//ai, bi, ci, 物品重量，利用价值，所属组数
int a[1001], v[1001], w[1001], f[1001];
vector<int> c[1001];
int main()
{
//两个数m, n，表示一共有n件物品，总重量为m
int m, n;
cin >> m >> n;
int i, j;
for(i = 1; i <= n; i++)
{
cin >> w[i] >> v[i] >> a[i];
c[a[i]].push_back(i);
}
for(i = 1; i <= 1000; i++)
for(j = m; j; j--)
for(auto k : c[i])
{
if(v[k] <= j)
f[j] = max(f[j], f[j - v[k]] + w[k]);
}
cout << f[m];
}
for(auto k : c[i])是一个基于范围的for循环，在C++中常见。这里是对它的分解：
auto: 这是一个自动类型推导关键字。在基于范围的for循环中，编译器会自动从c[i]中获取元素类型，并推断出k的类型。k: 这是循环中当前元素的临时变量名。在每次循环迭代时，k将持有c[i]中的一个元素。for(auto k : c[i]): 整体而言，这个循环从c[i]作为起点开始遍历中的每一个元素，并将每个元素赋值给变量k。
二维背包
爬楼梯
题目链接
参考代码：
int jumpFloor(int number) {
if(number == 1)
return 1;
if(number == 2)
return 2;
return jumpFloor(number - 1) + jumpFloor(number - 2);
}
斐波那契数列的实际应用
石子合并（区间DP）
题目链接
【参考代码】
#include <bits/stdc++.h>
using namespace std;
long long a[201] = {0}, s[201] = {0}, f[201][201]; // 定义数组a、s和f
// 递归函数solve，用于计算最小分割代价
long long solve(int l, int r)
{
if(f[l][r] != -1) // 如果已经计算过该子问题的解，直接返回结果
return f[l][r];
if(l == r) // 如果左右边界相等，说明只有一个元素，不需要分割，返回0
return 0;
long long ans = 1 << 30; // 初始化最小分割代价为一个较大的值 2的30次方
for(int m = l; m < r; m++) // 遍历所有可能的分割点m
// 计算左右两部分的最小分割代价，并取较小值
ans = min(ans, solve(l, m) + solve(m+1, r));
return f[l][r] = ans + s[r] - s[l-1]; // 将计算得到的最小分割代价存储到f数组中，并返回结果
}
int main()
{
memset(f, 255, sizeof(f)); // 初始化f数组为-1，表示未计算过任何子问题的解
int n;
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> a[i];
s[i] = s[i-1] + a[i]; // 计算前缀和数组s
}
cout << solve(1, n); // 调用solve函数计算最小分割代价，并输出结果
//cout << f[1][n]; 这个就是最终答案
}f[1][n]是最终答案，可以看到矩形右上角为最终答案f[1][n]
Q：9是怎么来的？
A：在5和3之间选一个最小值，前缀和数组是1,3,6。加上前缀和数组的最大值6
- ans = min(ans, solve(l, m) + solve(m+1, r));
- return f[l][r] = ans + s[r] - s[l-1];
Q：14怎么来的？
A：5和7选一个最小值，得出5。前缀和数组是1,3,6,10。f[2][4] = 14 = 5 + 10 (s[r]) – 1 (s[l-1])
9和14选一个最小值，加上前缀和数组的最大值10
- ans = min(ans, solve(l, m) + solve(m+1, r));
- return f[l][r] = ans + s[r] - s[l-1];
- 可以看出，若不加终止条件，会调用很多次递归函数，多次重复计算。优化后，用一个二维数组保存
最长公共子序列
题目链接
参考代码
class Solution {
public:
int lengthOfLIS(vector<int>& nums)
{
//最长上升子序列
int ans = 0;
int dp[2501] = {0};
int n = nums.size();
//需要从0开始，不然会报错：爆栈
for(int i=0; i < n; i++)
{
dp[i] = 1;
for(int j=0; j < i; j++)
{
if(nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
}
for(int i=0; i < n; i++)
{
ans = max(ans, dp[i]);
}
return ans;
}
};
最长公共子序列
题目链接
文章来源：https://www.toymoban.com/news/detail-789323.html
参考代码
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.length();
int m = text2.length();
int f[1001][1001];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(text1[i-1] == text2[j-1]) //i, j从1开始，string从1开始，要减1
//if(text1[i] == text2[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
return f[n][m];
}
};
运行结果
文章来源地址https://www.toymoban.com/news/detail-789323.html
最长回文子串
到了这里，关于第十三周代码（动态规划1）（持续更新）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
