行业知识
动态规划(蓝桥杯 C++ 题目 代码 注解)
2026-11-17 23:23:34
来源:互联网转载
���录
介绍:
题目一(数字三角形):
题目二(跳跃):
题目三(背包问题类型):
题目四(蓝肽子序列):
题目五(合唱队形):
题目六(最优包含):编辑
题目七(路径):
介绍:
动态规划(Dynamic Programming)是一种解决多阶段决策问题的算法思想,也是一种问题求解方法。
动态规划的基本思想是将问题划分为若干个子问题,然后通过计算子问题的最优解来得到原问题的最优解。这种划分子问题的方式,需要满足两个条件:1. 原问题的最优解包含子问题的最优解;2. 子问题之间必须相互独立,即子问题之间不存在重复计算。
动态规划的解决过程一般包括以下几个步骤:
1. 定义问题的状态:将原问题划分为若干个子问题,并定义每个子问题的状态。
2. 定义状态转移方程:根据子问题的定义,确定子问题之间的关系,即状态转移方程。
3. 初始化状态:确定初始状态的值。
4. 使用状态转移方程计算状态:根据状态转移方程,计算每个子问题的最优解。
5. 根据计算得到的状态,得出原问题的最优解。
动态规划能够有效解决一些具有重叠子问题和最优子结构性质的问题,它避免了重复计算,提高了算法的效率。常见的应用场景有最优路径问题、背包问题、最长公共子序列等。
题目一(数字三角形):
#include using namespace std;int a[200][200],f[200][200],n;int main(){ cin>>n; for(int i=1;ia[i][j]; f[1][1]=a[1][1]; for(int i=2;im; 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;igrid[i][j]; int ans = -999999; for(int t=0;t0 && j+y[t]>0) { ans = max(ans,grid[i+x[t]][j+y[t]]);//选从之前九个方向来中的最大值 } } if(ans!=-999999) grid[i][j]+=ans;//加上之前九个方向中最大的那一个 } coutb; int lena=a.length(),lenb=b.length(); int cnta=0,cntb=0; for(int i=0;i='A'&&a[i] a[j]) dp2[i] = max(dp2[i], dp2[j] + 1); } } for (int i = 1; i >t; int dp[1200][1200];//表示s中前i个字符,t中前j个字符最小修改次数 memset(dp,0x3f3f,sizeof(dp)); for(int i=0;i
上一篇:云服务器怎么使用安卓版
下一篇:怎么查服务器权限设置时间?