动态规划（蓝桥杯 C++ 题目 代码 注解）
目录
介绍：
题目一（数字三角形）：
题目二（跳跃）：
题目三（背包问题类型）：
题目四（蓝肽子序列）：
题目五（合唱队形）：
题目六（最优包含）：
题目七（路径）：
介绍：
动态规划（Dynamic Programming）是一种解决多阶段决策问题的算法思想，也是一种问题求解方法。
动态规划的基本思想是将问题划分为若干个子问题，然后通过计算子问题的最优解来得到原问题的最优解。这种划分子问题的方式，需要满足两个条件：1. 原问题的最优解包含子问题的最优解；2. 子问题之间必须相互独立，即子问题之间不存在重复计算。
动态规划的解决过程一般包括以下几个步骤：
1. 定义问题的状态：将原问题划分为若干个子问题，并定义每个子问题的状态。
2. 定义状态转移方程：根据子问题的定义，确定子问题之间的关系，即状态转移方程。
3. 初始化状态：确定初始状态的值。
4. 使用状态转移方程计算状态：根据状态转移方程，计算每个子问题的最优解。
5. 根据计算得到的状态，得出原问题的最优解。
动态规划能够有效解决一些具有重叠子问题和最优子结构性质的问题，它避免了重复计算，提高了算法的效率。常见的应用场景有最优路径问题、背包问题、最长公共子序列等。
题目一（数字三角形）：
#include <iostream>
using namespace std;
int a[200][200],f[200][200],n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>a[i][j];
f[1][1]=a[1][1];
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=a[i][j]+max(f[i-1][j],f[i-1][j-1]);//从左下或者从右下来
cout<<max(f[n][(n+1)/2],f[n][(n+2)/2]);//因为向左走与向右走的次数相差不超过一，所以走到中间
return 0;
}
题目二（跳跃）：
#include <iostream>
using namespace std;
int n,m,ans;
int main()
{
cin>>n>>m;
int grid[110][110];
int x[9] = {0,0,0,-1,-1,-1,-2,-2,-3};
int y[9] = {-1,-2,-3,0,-1,-2,0,-1,0};
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
cin>>grid[i][j];
int ans = -999999;
for(int t=0;t<9;++t)
{
if(i+x[t]>0 && j+y[t]>0)
{
ans = max(ans,grid[i+x[t]][j+y[t]]);//选从之前九个方向来中的最大值
}
}
if(ans!=-999999) grid[i][j]+=ans;//加上之前九个方向中最大的那一个
}
cout<<grid[n][m]<<endl;
return 0;
}
题目三（背包问题类型）：
背包问题（介绍+例题+代码+注解）-CSDN博客
题目四（蓝肽子序列）：
#include<iostream>
using namespace std;
int dp[1100][1100];//代表到a字符串中第i个单词和b字符串中第j个单词时的最长公共序列
string a,b;
string worda[1100],wordb[1100];
int main()
{
cin>>a>>b;
int lena=a.length(),lenb=b.length();
int cnta=0,cntb=0;
for(int i=0;i<lena;i++)//拆分第一个字符串
{
if(a[i]>=’A’&&a[i]<=’Z’)
cnta++;
worda[cnta]+=a[i];
}
for(int i=0;i<lenb;i++)//拆分第二个字符串
{
if(b[i]>=’A’&&b[i]<=’Z’)
cntb++;
wordb[cntb]+=b[i];
}
for(int i=1;i<=cnta;i++)
for(int j=1;j<=cntb;j++)
{
if(worda[i]==wordb[j])//相等则加一
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//不相等，则看是不选哪个时公共子序列更大
}
cout<<dp[cnta][cntb];
}
题目五（合唱队形）：
#include<iostream>
#include<algorithm>
using namespace std;
int n, dp1[1010], dp2[1010];
int a[1010];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
cin>>a[i];
for (int i = 1; i <= n; i++)//从左往右递增子序列
{
dp1[i] = 1;
for (int j = 1; j < i; j++)
{
if (a[i] > a[j])
dp1[i] = max(dp1[i], dp1[j] + 1);
}
}
for (int i = n; i >= 1; i–)//从右往左递增子序列
{
dp2[i] = 1;
for (int j = n; j > i; j–)
{
if (a[i] > a[j])
dp2[i] = max(dp2[i], dp2[j] + 1);
}
}
for (int i = 1; i <= n; i++)//以第i个人为最高的
a[i] = dp1[i] + dp2[i] -1;//i重复算了一次，减掉
sort(a + 1, a + 1 + n);//小到大排序
cout << n – a[n] << endl;
}
题目六（最优包含）：
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
string s,t;
cin>>s>>t;
int dp[1200][1200];//表示s中前i个字符，t中前j个字符最小修改次数
memset(dp,0x3f3f,sizeof(dp));
for(int i=0;i<=s.size();i++)
dp[i][0]=0;
for(int i=0;i<s.size();i++)
{
for(int j=0;j<t.size();j++)
{
if(s[i]==t[j])//相等，直接继承
dp[i+1][j+1]=dp[i][j];
else
dp[i+1][j+1]=min(dp[i][j+1],dp[i][j]+1);//选择不修改i的修改次数小还是选择修改i的次数小
}
}
cout<<dp[s.size()][t.size()];
}
题目七（路径）：
#include<iostream>
using namespace std;
int gcd(int x, int y)//辗转相除法，求最大公约数
{
return !y ? x : gcd(y, x % y);
}
int main()
{
int f[2030]={0};//记录到该点的最短距离
for(int i=1;i<=2021;i++)
for (int j = i + 1; j <= i + 21; j++)
{
if (j > 2021)
break;
if (f[j] == 0)
f[j] = f[i] + i * j / gcd(i, j);
else
f[j] = min(f[j], f[i] + i * j / gcd(i, j));
}
cout << f[2021] << endl;
- 海报
免责声明：本站除原创代码外的资源均收集于网络，不保证代码的完整性和可用性，只做学习和交流使用，版权归原作者所有，请在下载后24小时之内自觉删除。若作商业用途，请购买正版，由于未及时购买正版授权发生的侵权行为，与本站无关。本站的内容如果侵犯了您的权益，请及时告知我们，我们即刻处理！
少儿编程课程 儿童编程教育 编程启蒙班 青少年编程培训 Scratch编程学习 Python少儿编程 机器人编程教育 编程思维训练 编程游戏化教学 在线少儿编程平台 儿童编程软件推荐 编程竞赛准备 编程兴趣班 逻辑思维与编程 少儿编程教材 编程与STEM教育 编程技能培养 编程语言入门（如：JavaScript少儿版） 家长如何选择少儿编程课 编程对孩子未来的影响 编程项目实践 编程与创造力培养 编程思维在日常生活中的应用 编程教育专家观点 编程教育趋势分析 少儿编程社区 编程夏令营 编程冬令营 编程学习路线图 编程证书考试 少儿编程启蒙 儿童图形化编程（如Scratch编程） 青少年Python编程 编程基础班（针对小学生） 编程进阶课程（适合高年级学生） 机器人编程工作坊 AI启蒙编程课 逻辑思维编程游戏 编程与数学能力提升 编程思维训练营 编程解决问题的能力培养 在线互动编程课堂 编程项目实战演练 编程创意工坊 编程教育APP推荐 编程教育论坛与社区 编程兴趣小组 编程竞赛辅导 编程证书考试准备 编程教育政策解读 编程教育家长指南 编程与跨学科学习（STEM/STEAM） 编程与创新能力培养 编程与未来职业规划 编程教育师资培训 编程教育研究成果分享 编程教育行业标准 编程教育市场动态 编程教育投资前景 编程教育公益项目
微点点-专业的知识付费平台 » 动态规划（蓝桥杯 C++ 题目 代码 注解）
少儿编程课程 儿童编程教育 编程启蒙班 青少年编程培训 Scratch编程学习 Python少儿编程 机器人编程教育 编程思维训练 编程游戏化教学 在线少儿编程平台 儿童编程软件推荐 编程竞赛准备 编程兴趣班 逻辑思维与编程 少儿编程教材 编程与STEM教育 编程技能培养 编程语言入门（如：JavaScript少儿版） 家长如何选择少儿编程课 编程对孩子未来的影响 编程项目实践 编程与创造力培养 编程思维在日常生活中的应用 编程教育专家观点 编程教育趋势分析 少儿编程社区 编程夏令营 编程冬令营 编程学习路线图 编程证书考试 少儿编程启蒙 儿童图形化编程（如Scratch编程） 青少年Python编程 编程基础班（针对小学生） 编程进阶课程（适合高年级学生） 机器人编程工作坊 AI启蒙编程课 逻辑思维编程游戏 编程与数学能力提升 编程思维训练营 编程解决问题的能力培养 在线互动编程课堂 编程项目实战演练 编程创意工坊 编程教育APP推荐 编程教育论坛与社区 编程兴趣小组 编程竞赛辅导 编程证书考试准备 编程教育政策解读 编程教育家长指南 编程与跨学科学习（STEM/STEAM） 编程与创新能力培养 编程与未来职业规划 编程教育师资培训 编程教育研究成果分享 编程教育行业标准 编程教育市场动态 编程教育投资前景 编程教育公益项目
微点点-专业的知识付费平台 » 动态规划（蓝桥杯 C++ 题目 代码 注解）
