c++ 动态规划 小总结

之前学习了一些动态规划的知识点，在此做一个小总结。

定义

动态规划，就是通过把原问题分解成若干相关子问题（所有这些问题在一定意义上答案固定），再利用已知子问题的答案，最终得到原问题答案的一种算法，是解决某一类具有最优子结构，无后效性问题的思想。

而在动态规划中，有两个重要的概念。

状态

动态规划的状态可以笼统地解释成“问题所在的局面”。状态具有明确良好的定义，一般可以写成：（用变量表示的)所在局面的（最优）答案，或者满足某种性质的方案数。如果不知道怎么确定状态，可以考虑套用最朴素的搜索算法中的状态。

状态的答案应该只依赖状态定义的局面和一些状态以外的常量。也就是说，在一般情况下，状态变化并不会影响状态以外的量，该状态之后的演变不受这个状态之前决策的影响。因此，如果要用动态规划来解决一道题，应把所有可能的变动加入状态的定义中去。

状态转移方程

因为要求解最终状态的答案，所以状态之间需要存在某些关系。一般把这样的计算关系称
作转移，计算式称为（状态）转移方程。状态转移方程一般具有它自己的意义，体现的是从一个状态到另一个状态的变化。

对于最优化问题来说，转移方程的目的就是找到最优的前继情况的答案。在无特殊性质的情况下，转移方程需要找出所有前继情况并取出最优答案。若前继状态的最优答案不能转移成为当前状态的最优答案，则该问题（至少目前这个定义的状态)不满足用动态规划解决的要求。前继状态最优解与当前状态之间最优解的关联性被称为动态规划的最优子结构性质。

对于计数问题来说，转移方程的目的就是不遗漏不重复地统计局面的所有方案数。一般来说，转移方程需要找出所有前继情况并进行恰当地组合计数。

转移存在两种方式，一种是发送型转移，另一种是接收型转移。前者枚举状态的后继，并计算对后继的贡献；后者枚举状态的前继，当即计算出状态的答案。

例题

数字金字塔

写一个程序查找一个数字金字塔从最高点到底部任意处结束的路径，使路径经过数字的和最大。
每一步可以从当前点走到左下方的点也可以到达右下方的点。

一种动态转移方程：

dp[i][j]=max ( dp[i-1][j-1] , dp[i-1][j] ) + a[i][j];（不要忘了防止越界）

此处的i,j表示的是第i行第j列，dp数组表示的是当前到底i行第j列时的最大和。每一步可以从当前点走到左下方的点也可以到达右下方的点，也就是说，一个数可以从它的右上角或左上角的最大和中挑出最大的一个进行选择，最后时直接从dp[n][1]循环到dp[n][n]，找到最大的即可。示例代码如下：

#includeusing namespace std;int mmax[1050][1050],a[1050][1050],n,mmmax;int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j>a[i][j]; mmax[i][j]=max(mmax[i-1][j-1],mmax[i-1][j])+a[i][j]; } for(int i=1;immmax)mmmax=mmax[n][i]; cout<<mmmax; return 0;}

最长上升子序列

一个数的序列bi​，当b1​<b2​<...<bS​的时候，我们称这个序列是上升的。对于给定的一个序列(a1​,a2​,...,aN​)，我们可以得到一些上升的子序列(ai1​,ai2​,...,aiK​)，这里1≤i1​ ,对于给定的序列，求出最长上升子序列的长度。

一种动态转移方程：

if ( a[j] mmax[i] ) mmax[i] = mmax[j];

#includeusing namespace std;int mmax[1050],a[1050],n,mmmax;int main(){ cin>>n; for(int i=1;i>a[i]; for(int j=1;j<i;j++) if(a[j]mmax[i])mmax[i]=mmax[j]; mmax[i]++; if(mmax[i]>mmmax)mmmax=mmax[i]; } cout<<mmmax; return 0;}

#includeusing namespace std;int dp[1050][1050];string a,b;int main() { cin>>a>>b; for(int i=1;i<=a.length();i++){ for(int j=1;j<=b.length();j++){ if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } cout<<dp[a.length()][b.length()]; return 0;}