动态规划是一种用来解决最优化问题的算法思想，其会记录下子问题的最优解，综合子问题的最优解得到最优解。
上面有两个关键，划分子问题和记录子问题，其中划分子问题有一个重要的状态转移方程。
一般解决步骤如下：
1.确定维数，确定dp数组。
2.每一维采用下面表述，为i或者前i。
3.之后问题可以描述为dp[i]为恰好为i（或者前i）的XXX（问题描述），然后思考dp[i-1]得出状态转移方程。
动态规划的题目主要可能得多看习题领悟，这里针对典型例题来领悟动态规划的过程。
最大连续子序列和
问题：给定一个序列（整数或浮点数），求出其中连续的子序列和最大的那一个。
例：序列{-10 1 2 3 4 -5 -23 3 7 -21}，其最大的连续子序列为{1 2 3 4}或{3 7}，最大和为10。
首先涉及到一个序列，应该是一维问题，应该可以用一个一维数组来记录子问题的最优解，第二步dp[i]表述恰好为i时在最大连续和(前i肯定不合适），第三步思考dp[i-1]和dp[i] 的关系，如果dp[i-1]<0,显然dp[i]=a[i],否则加上前面的dp[i-1]dp[i]肯定更大，于是状态转移方程得出。最后问题思考的序列完找出dp[i]最大的即可。
附代码如下：
#include<iostream> #include<algorithm> using namespace std; const int maxn=10001; int dp[maxn],a[maxn];//dp[i] 表示结尾恰好为i时最大和 int main(){ int n; while(scanf("%d",&n),n){ fill(dp,dp+n+1,-1); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int max=-100000,k=-1; for(int i=1;i<=n;i++) { if(dp[i-1]>0)dp[i]=dp[i-1]+a[i]; //状态转移 else dp[i]=a[i]; if(max<dp[i]) //更新最大值 { max=dp[i]; k=i; } } if(max<0)printf("%d %d %d\n",0,a[1],a[n]); else { printf("%d ",max); for(int i=k;max!=0||dp[i-1]==0;i--) { max-=a[i]; if(max==0&&dp[i-1]!=0) printf("%d ",a[i]); } printf("%d\n",a[k]); } } return 0; }
最长上升子序列
问题：给一个数组a1, a2 … an，找到最长的不下降子序列ab1<ab2<=… <abk，其中b1<b2<…bk，输出长度即可。
思考：维度应该一维，dp[i]应该表示以i结尾的最大不下降子序列长度，前面如果数字都比a[i]大那么dp[i]就为1，否则只要前面dp[j]对应a[j]<a[i],且长度＋1后比dp[i]长度大，说明a[i]可以接在a[j]后面得到最大长度。
代码如下：
#include<iostream> #include<algorithm> using namespace std; const int maxn=5001; char a[maxn],dp[maxn]; int main(){ int n,length=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]) ; fill(dp,dp+n+1,0); a[0]=-1; for(int i=1;i<=n;i++) { for(int j=0;j<i;j++) { if(a[j]<a[i]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; } if(length<dp[i])length=dp[i]; } printf("%d\n",length); return 0; }
最长公共子序列
问题：给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB
则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA
分析：两个字符串，应该是二维，dp[i][j]应该表示为两个字符串第i，j位之前的最长公共子序列数，如果两个字符串第ij位相等，长度肯定是dp[i-1][j-1]+1，否则应该是dp[i-1][j]或者dp[ii][j-1]中的最大值。
代码如下:
#include<iostream> #include<algorithm> #include<string> using namespace std; const int maxn=101; string a,b; int dp[maxn][maxn]; int main(){ while(cin>>a>>b){ fill(dp[0],dp[0]+maxn*maxn,0); int n=a.size(),m=b.size(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1]+1; else { if(dp[i][j-1]>dp[i-1][j]) dp[i][j]=dp[i][j-1]; else dp[i][j]=dp[i-1][j]; } } } a.clear();b.clear(); cout<<dp[n][m]<<endl;} return 0; }
简单取了三个例子，此外还有最长回文子串、dag最长路、背包问题的应用。分别教会了我变换更新方式、递推和递归、打印路径，这里一定多练习。
