动态规划（蓝桥杯 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;
}