深入思考，仔细读题，抽象化问题本质，寻找相同点。
DP的话，思考一种可以完美概括影响又没有多存无意义信息的表示。
所以要分析什么信息对后来的计算有用。
T1：
题意：
判断一棵子树所有节点的编号是否刚好为一完整区间。
分析：
简单分析一下，可以一次dfs搞定，就上传最小节点编号，最大节点编号，然后比较一下子节点个数即可。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n,m) for(int i=n;i<m;i++)
#define eachrev(i,n,m) for(int i=n;i>m;i--)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "A"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,fa,son,ans;
int fr[Maxn],des[Maxn],tov[Maxn],mini[Maxn],maxn[Maxn],siz[Maxn],rd[Maxn];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void addedge(int cur)
{
fa=read();son=read();
tov[cur]=fr[fa];fr[fa]=cur;des[cur]=son;
rd[son]++;
}
void init()
{
n=read();
each(i,1,n)
addedge(i);
}
void dfs(int u)
{
mini[u]=maxn[u]=u;
siz[u]=1;
for(int i=fr[u];i;i=tov[i]){
int v=des[i];
dfs(v);
mini[u]=min(mini[u],mini[v]);
maxn[u]=max(maxn[u],maxn[v]);
siz[u]+=siz[v];
}
if(maxn[u]-mini[u]+1==siz[u])ans++;
}
void work()
{
each(i,1,n+1)
if(!rd[i])
dfs(i);
printf("%d",ans);
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}T2：
题意：
给定一个序列中任意两相邻元素的大小关系（可能为“未知”），求满足给定条件的n的全排列序列个数。
分析：
显然来了就能想出DP套路：f[i][j]表示前I个，最后一个为J的方案数。然而我们会发现这样有后效性。
然后思考一下，真正会对后面产生影响的是前面生成的序列本身吗？其实并不是，如果一个已生成的序列任意两元素之间的相对大小关系确定了，那么这个序列其实对后面的影响也就完全被表示出来了，因为若某一种情况不能选，我们还可以给每个数都加一，总会可以加入。
最终思路：f[i][j]，j表示在最后一位的数在前面共i个数中大小排第j位。然后分类讨论即可。
注意：若第i位为第j大，则f[i-1][j]可以在I的时候被取到，因为那时候的j会变成新序列中的j+1;
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n,m) for(int i=n;i<m;i++)
#define eachrev(i,n,m) for(int i=n;i>m;i--)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "B"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e3+5;
const int modd=1e9+7;
int n,sum,ans,f[Maxn][Maxn];
char a[Maxn];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
scanf("%s",a+1);
n=strlen(a+1)+1;
}
void work()
{
each(i,0,n+1)
f[0][i]=1;
each(i,1,n){
sum=0;
if(a[i]=='I'){
each(j,1,i+2){
(f[i][j]+=sum)%=modd;
(sum+=f[i-1][j])%=modd;
}
}
else if(a[i]=='D'){
eachrev(j,i,0){
(sum+=f[i-1][j])%=modd;
(f[i][j]+=sum)%=modd;
}
}
else{
each(j,1,i+1)
(sum+=f[i-1][j])%=modd;
each(j,1,i+2)
(f[i][j]+=sum)%=modd;
}
}
each(i,1,n+1)
(ans+=f[n-1][i])%=modd;
printf("%d",ans);
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}T3:
题意：
在A中取长度为A,B LCS长度的子序列，求共有哪些序列在B中可被找到。
分析：
先走一次预处理f[i][j]存A前i位B前j位的LCS长度，然后再跑一次g[i][j]存对于A前I位B前j位所求的值是多少。
这时候，对于正在枚举的g[i][j]，考虑i是否被取（因为真正被计数的是A串中个数），若f[i][j]==f[i-1][j]，则可以不取i;若f[A中前一个出现a[i]的位置-1][j]==f[i][j]，则可以取i;
对于满足的情况加上对应的方案数即可。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define ll long long
#define inf 2e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define each(i,n,m) for(int i=n;i<m;i++)
#define eachrev(i,n,m) for(int i=n;i>m;i--)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "C"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e3+5;
const int modd=1e9+7;
int lena,lenb;
int f[Maxn][Maxn],g[Maxn][Maxn],pos[30],pre[Maxn][30];
char a[Maxn],b[Maxn];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
cin.getline(a+1,Maxn);
cin.getline(b+1,Maxn);
lena=strlen(a+1);
lenb=strlen(b+1);
each(i,0,lena+1)
g[i][0]=1;
each(i,0,lenb+1)
g[0][i]=1;
}
void work()
{
each(i,1,lena+1)
each(j,1,lenb+1){
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
/*each(i,1,lena+1)
each(j,1,lenb+1){
pos[a[i-1]-'a']=max(pos[a[i-1]-'a'],1);
if(f[i][j]==f[i-1][j])
(g[i][j]+=g[i-1][j])%=modd;
if(f[i-1][pos[a[i-1]-'a']-1]+1==f[i][j])
(g[i][j]+=g[i-1][pos[a[i-1]-'a']-1])%=modd;
pos[a[i-1]-'a']=j;
}*/
minus(pos);
each(i,1,lenb+1) {
pos[b[i] - 'a'] = i;
each(j,0,26) pre[i][j] = pos[j];
}
each(i,1,lena+1){
each(j,1,lenb+1) {
g[i][j] = 0;
if(f[i][j] == f[i - 1][j]) (g[i][j]+=g[i-1][j])%=modd;;
int p = pre[j][a[i] - 'a'];
if(p != -1 && f[i - 1][p - 1] + 1 == f[i][j])
(g[i][j]+=g[i-1][p-1])%=modd;
}
}
printf("%d",g[lena][lenb]);
}
void debug()
{
//
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
//debug();
return 0;
}