动态规划（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 串中出现互不重叠的 0 和 1 子串最多，输出子串个数。
输入格式
输入一行包含一个字符串。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于所有评测用例，1≤n≤10^6。
输入样例：
1110?0
输出样例：
2
样例解释:
如果在问号处填
0，则最多出现一个00和一个11：111000。
解题思路：
主要利用动态规划思想，定义一个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问题只要能找到状态转移方程就基本解决了，博主感觉最难的还是状态的定义与描述。多做题积累经验，文章代码实现或者思路有错误的地方，请各位大佬指出，感激不尽*~*。
执笔至此，感触彼多，全文将至，落笔为终，感谢大家的支持。
