动态规划
一、几个要点
1、主体思想：同一件事件不做第二次；
2、状态表示：用问题的某些特征参数描述当前的问题；
3、状态转移方程：
状态值之间的递推关系（计算关系）
边界条件 递推顺序
4、实现方式
自顶向下：记忆化的搜索形式。
自底向上：递推形式。
二、可以使用动态规划的题目特点：
1、一个大问题可以划分为若干子问题
最优子结构
子问题：性质一样，但是规模变小的问题。
2、在计算时子问题有重叠
重叠子结构
例1 、hdu2084 数塔问题
1、递归：F（x，y）=max{F（x+1，y），F（x+1，y+1）}+A[x，y]；------超时
2、自下而上记忆化思想（动态规划思想）保证每一个状态最多处理一次。
//基础的DP数塔问题 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 103 using namespace std; int num[maxn][maxn],n,dp[maxn][maxn]; /*int f(int x,int y) 注释部分为递归超时代码 { if(x==n) return num[x][y]; else //注意这里不是num[x+1][y]和num[x+1][y+1]而是函数的递归调用。 { //return max(f(x+1,y),f(x+1,y+1))+num[x][y];//递归,保存每一层的结果，其实遍历了整个数塔; res[x]=f(x,y); } }*/ int main() { int t,i,j,ans; cin >> t ; while(t--) { ans=0; cin >> n; for(i=1;i<=n;i++) for(j=1;j<=i;j++) cin >> num[i][j]; memset(dp,0,sizeof(dp)); //初始化 for(i=1;i<=n;i++) dp[n][i]=num[n][i]; //数塔最后一层赋值给dp的最后一层---后面数组就不会越界。 for(i=n-1;i>=1;i--) //[1-n]的数塔，从数塔的倒数第二层开始 { for(j=1;j<=i;j++) //每层数塔 { //状态转移方程 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+num[i][j];//将下一层的数中可走路径(两两之间选较大的) 加到这一层 } //记录了每一层选择的路径结果 } cout << dp[1][1] << endl; //ans=f(0,0); //cout << ans << endl; } return 0; }
hdu1176 免费陷阱 http://acm.hdu.edu.cn/showproblem.php?pid=1176
/*基础dp,免费掉馅饼*/ #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define maxn 100005 //因为0< T < 100 000 using namespace std; int dp[maxn][13]; int main() { int n,i,j,s,t,m; while(cin >> n,n) { m=0; for(i=1;i<=n;i++) { cin >> s >> t; if(m<t) m=t; //m记录下掉馅饼的最后时刻，即dp的最后一层 dp[t][s]++; //每一秒路径上的情况记录下来 } for(i=m-1;i>=0;i--) //从倒数第二层开始,是m层，不是n,n只是输入组数 { for(j=0;j<11;j++) { //每一层记录从下一层走上来的最优结果 //这里的j-1其实数组越界了，但是hdu没有报错，还AC了！喵喵喵？？？ dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]); } //状态转移方程 } cout << dp[0][5] << endl; //每一层的最优结果到初始位置最优得answer memset(dp,0,sizeof(dp)); } return 0; }
PS：上述数组越界AC了，经多方讨论，以及自爆（= =），事实证明DEV并没有报RE，CB也没有，而且越界访问的值，有的编译器是你定义的其他变量的值，也就是说越界可能会导致你其他变量的值改变（interesting），大概是分配内存时，分配的相邻了吧，但有些编译器是访问的是0 ；越界过多就会爆。
例2、最长上升子序列
1、状态定义：F[ i ]表示序列A[1……i ]的一个最长递增序列的长度（以A[ i ]结尾）；
状态转移：F[ i ] =max{F[ j ] + 1} j<i A[ j ] < A[ i ]
hdu1257最少导弹拦截系统 http://acm.hdu.edu.cn/showproblem.php?pid=1257
/*最长上升子序列LIS*/ #include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <algorithm> #define maxn 100005 using namespace std; int dp[maxn],num[maxn];//dp[i]定义为以ai为结尾的最长上升子序列的长度 int main() { int n,i,j,ans; //freopen("Atext.in","r",stdin); while(cin >> n) { ans=0; for(i=0;i<n;i++) { cin >> num[i]; dp[i]=1;//每一个以ai为结尾的LIS只有两种情况，一种是他自身 } //另一种是它前面比它小的数的LIS加上ai for(i=0;i<n;i++) { //dp[i]=1的赋值也可以放到这里 for(j=0;j<i;j++) //对每一个ai的前面走到它的路径循环记录 { if(num[j]<num[i])//选出以ai结尾的最长的路径保存 dp[i]=max(dp[j]+1,dp[i]); } ans=max(dp[i],ans); //记录各个路径的最大值，即LIS } cout << ans << endl; } return 0; }
例3、最长公共子序列
1、状态定义：F[ i,j ]表示序列A[ 1……i ]与B[ 1……j ]的最长公共子序列长度；
状态转移：计算F[ i , j ]时
若A[ i ] =B[ j ] F[ i , j ]=F[ i-1, j-1] +1;
A[ i ] != B[ j ] F[ i ,j ]=max{F [ i-1，j ] ，F[ i ，j -1]}
例4、背包九讲
01背包，多重背包，完全背包……