【动态规划算法】蓝桥杯填充问题(C/C++)

简介: 【动态规划算法】蓝桥杯填充问题(C/C++)

动态规划(Dynamic Programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常用于优化那些具有重叠子问题和最优子结构性质的问题。

动态规划的基本步骤:

1. 问题分解:将复杂的原问题分解为若干个相对简单的子问题。

2. 最优子结构:问题的最优解包含其子问题的最优解。

3. 状态定义:描述问题的状态,dp数组定义为几维,代表什么含义。

4. 状态转移方程:找出状态之间的关系,这是动态规划算法的核心,只要有了状态转移方程,那么动态规划就成功了一大半了。

5. 边界条件:确定初始状态或边界条件,一般确定dp[0]/dp[0][0],给一个初始值,还有就是确定它要更新到哪一个状态就完成了。

6. 计算顺序:确定各状态按照什么顺序进行计算,以保证在计算当前状态时,所需要的子状态已被计算。

7. 构造最优解:根据子问题的最优解,构造原问题的最优解。

动态规划的常见问题类型:

动态规划的问题在算法竞赛中非常多,特别是蓝桥杯,几乎每一年都需考,当需要学习蓝桥杯时,建议多去学习学习动态规划问题。在动态规划问题中,有的问题非常简单都是模板题,例如背包问题、LCS、LIS等等,但是也有比较难的题,例如数位DP、DP的优化问题、四边形不等理论等这种难题就需要根据自身量力而行了。比如四边形不等理论这个东西博主连听说过都没有,还是在书上看到的,学习动态规划关键就是多做题积累,去做完题总结,看它的DP是如何定义的,如何状态转移的,下面列举几个常见的DP问题。

1. 背包问题:包括0/1背包、完全背包、多重背包问题等。

2. 最长递增子序列:找出序列中最长的严格递增子序列。

3. 最短路径问题:在加权图中找到两点之间的最短路径。

4. 矩阵链乘问题:计算矩阵序列的乘积,并找出最优的乘法顺序。

5. 硬币找零问题:使用最少的硬币数量来凑成特定的金额。


动态规划是一种非常强大的算法,它的变化性很强,我们要根据题目实际情况进行选择行使用动态规划,定义的状态是什么,表示什么含义,状态如何转移。下面我们以第十四届蓝桥杯省赛大学C组(C/C++)填充这一题为例题,进行讲解动态规划。

原题链接:填充

有一个长度为 n 的 01 串,其中有一些位置标记为 ?,这些位置上可以任意填充 0 或者 1,请问如何填充这些位置使得这个 01 串中出现互不重叠01 子串最多,输出子串个数。

输入格式

输入一行包含一个字符串。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于所有评测用例,1≤n≤10^6。

输入样例:

1110?0

输出样例:

2

样例解释:

如果在问号处填 0,则最多出现一个 00 和一个 11111000


解题思路:

主要利用动态规划思想,定义一个dp[i]表示遍历到第i个位置的最大字串个数。第i个位置可以由前一个位置转移,分下面三种情况:


1.如果当前位置为0,它前一位三种情况0,1,?,当前一位为0或?时可以凑成字串,dp[i]=dp[i-1]+1,否则无法凑成字串dp[i]=dp[i-1]。


2.如果当前位置为1,它前一位三种情况0,1,?,当前一位为1或?时可以凑成字串,dp[i]=dp[i-1]+1,否则无法凑成字串dp[i]=dp[i-1]。


3.如果当前位置为?,它前一位三种情况0,1,?,当前一位为0、1或?时可以凑成字串,dp[i]=dp[i-1]+1,否则无法凑成字串dp[i]=dp[i-1]。


我们每次把能够凑成字串的位置都标记为2,防止重复利用。


代码实现:

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e6+5;
string s;
int res;
int dp[N];
int main(){
  cin>>s;
  for(int i=1;i<s.size();i++){
    if(s[i]=='0'){//第一种情况
      if(s[i-1]=='0'||s[i-1]=='?'){
        dp[i]=dp[i-1]+1;
        s[i]=s[i-1]='2';
      }
      dp[i]=max(dp[i],dp[i-1]);
    }
    if(s[i]=='1'){//第二种情况
      if(s[i-1]=='1'||s[i-1]=='?'){
        dp[i]=dp[i-1]+1;
        s[i]=s[i-1]='2';
      }
      dp[i]=max(dp[i],dp[i-1]);
    }
    if(s[i]=='?'){//第三种情况
      if(s[i-1]=='0'||s[i-1]=='1'||s[i-1]=='?'){
        dp[i]=dp[i-1]+1;
        s[i]=s[i-1]='2';
      }
      dp[i]=max(dp[i],dp[i-1]);
    }
  }
  cout<<dp[s.size()-1]<<endl;
  return 0;
}

DP问题只要能找到状态转移方程就基本解决了,博主感觉最难的还是状态的定义与描述。多做题积累经验,文章代码实现或者思路有错误的地方,请各位大佬指出,感激不尽*~*。


执笔至此,感触彼多,全文将至,落笔为终,感谢大家的支持。

相关文章
|
22天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
38 2
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
71 2
动态规划算法学习三:0-1背包问题
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
72 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
2月前
|
机器学习/深度学习 算法 关系型数据库
第十五届蓝桥杯C++B组省赛
第十五届蓝桥杯C++B组省赛
94 14
|
2月前
|
算法 C++
2022年第十三届蓝桥杯大赛C/C++语言B组省赛题解
2022年第十三届蓝桥杯大赛C/C++语言B组省赛题解
46 5
|
2月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
72 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
2月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
148 0
动态规划算法学习二:最长公共子序列
|
2月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
519 0
高精度算法(加、减、乘、除,使用c++实现)
|
2月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
114 0
|
2月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)