动态规划训练

本周过生日又国庆，玩了三天。。。 但是多少还是做了些题练习dp，都是些经典题型

基础题型：

最长递增子序列:

dp[i]表示以i为末尾的最长子序列有多长

状态转移方程：

for(int i=2;i<=n;i+){ int max=0; for(j=1;j<i;j++) if(max<dp[j]&&a[j]<a[i]) max=dp[j]; dp[i]=max+1; if(dp[i]>ans) ans=dp[i]; }

自顶向下走三角形-poj1163：

递推：

因为每层都要遍历，所以可以从最底层开始

dp[i][j]就是第i层第j个从底层上来的数字和

for(int i=n-1;i>=1;i--) for(int j=1;j<=i;j++) dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);

递归：

int dps(int i,int j){ if(i==n) return a[i][j]; dp[i][j]=max(dps(i+1,j),dps(i+1,j+1); }

区间dp：

区间上DP，它的主要思想就是先在小区间进行DP得到最优解，然后再利用小区间的最优解合并求大区间的最优解。

dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+s[i][j];

for(int i=1;i<=n;i++) { dp[i][i]=初始值 } for(int len=2;len<=n;len++) for(int i=1;i<=n;i++) { int j=i+len-1; if(j>n) break; for(int k=i;k<j;k++) dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]); }

树状dp：

树上的动态规划（树形dp）大致分为三类

1.最大独立集

2.树的重心（质心）

3.树的最长路径（最远点对）

建树：

cin>>a>>b; if(a==0&&b==0) break; tree[b].push_back(a); father[a]=b;

dfs解决总权值最大:

void dfs(int u){ dp[u][0]=0; dp[u][1]=0; for(i=0;i<tree[u].size();i++){ int son=tree[u][i]; dfs(son); dp[u][0]+=max(dp[son][1],dp[son][0]); dp[u][1]+=dp[son][0]; } }

几个不太熟练的题型都练了一下