DP

多维dp可以使用坐标来表示状态，P1004，就可以将每个方格的f值开为f[i][j][k][l],将两个点分别在（i，j）与（k，l）的状态表示，进行状态转移，对于特定的情况，可以进行降维，P1006，由于传纸条是只能向下和向右传递，所以到达每个点的步数是一定的，为i+j-1（初始点不同表示方法不同，也可以是i+j-2）,这样就可以开一个三维数组，f[k][i][j],用k来表示到达这个状态的步数，i，j表示该状态两个点的行（列）数，由于步数与行列数的关系，可以算出该点的行列坐标，进行与四维相同的转移即可，另外一点就是，在这两个题中是要求不能到达同一点，但要求的其实是总和，所以不管哪一点进入该状态都可以，判断（i==j）f-=该点的val；

p1006转移代码

    for(int k=2;k<=n+m-1;k++)
    for(int i=1;i<=n&&i<=k;i++)
    for(int j=1;j<=n&&j<=k;j++)
    {
        f[k][i][j]=max(max(max(f[k-1][i-1][j-1],f[k-1][i][j-1]),f[k-1][i-1][j]),f[k-1][i][j])+val[k-i+1][i]+val[k-j+1][j];
        if(i==j)f[k][i][j]-=val[k-j+1][j];
    }
    cout<<f[n+m-1][n][n];

 区间DP【我是谁，我在那？

对于区间的状态转移个人认为最主要的是最小单元和合并方式，以及状态表示，对于一个区间的操作，如何才能借此推出下一个区间就是一个关键性问题，由于是区间的操作，有可能会出现向左与向右的问题，所以可能会需要加入一个维度来表示区间的左与右，P1220，就是一个典型的在区间上表示左右的题；

对于大多数的区间DP，记忆化搜索与递推都是可以转换的，记忆化搜索是去除，而递推则是加入，比如P1005，就是一个两种方法均可。对与递推，还有注意一部分的倒序，这样才能保证无后效性，

区间DP的转换性也是很强的，当一个矩阵行与行之间没有关联时，就可以转变为每一行的区间DP，矩形取数就是这样的一个题。

P1220

f[s][s][0]=0;f[s][s][1]=0;
for(int i=s;i>=1;i--)for(int j=i+1;j<=n;j++)
    {
f[i][j][0]=min(f[i+1][j][0]+(a[i+1]-a[i])*t[i+1][j]
              ,f[i+1][j][1]+(a[j]-a[i])*t[i+1][j]);
f[i][j][1]=min(f[i][j-1][0]+(a[j]-a[i])*t[i][j-1]
              ,f[i][j-1][1]+(a[j]-a[j-1])*t[i][j-1]);
    }
    cout<<min(f[1][n][1],f[1][n][0]);

P1005

a[0]=1;f(i,m)a[i]=a[i-1]*2;
f(i,n)
{    
    for(int r=1;r<=m;r++)
    for(int l=r;l>=1;l--)
    {    k=m-(r-l);
    f[l][r]=max(f[l+1][r]+num[i][l]*a[k],f[l][r-1]+num[i][r]*a[k]);
    }
    ans+=f[1][m];
    f(k,m)f(o,m)f[k][o]=0;
}

 做了一点树形DP的题，觉得树形DP感觉很少会出现其他类型，【其实是太弱了

一类是类似没有上司的舞会，和最大独立集有关的题，另外一类就是树上的分组背包，通过枚举分给每一个子树的权值，感觉很套化，多练一练掌握一下

而且树上背包个人感觉记忆化搜索更优，比较舒服

P1270,

void init(int cnt)
{
    int a;
    cin>>a>>val[cnt];
    tme[cnt]=a*2;
    if(!val[cnt])
    {
        init(cnt>>1);
        init(cnt>>1|1);
    }
}
int dfs(int cnt,int tot)
{if(f[cnt][tot]>0||!tot)return f[cnt][tot];    
if(val[cnt])return f[cnt][tot]=min(val[cnt],(tot-tme[cnt])/5);
    for(int i=0;i<=tot-tme[cnt];i++)
    f[cnt][tot]=max(f[cnt][tot],dfs(cnt<<1,i)+dfs(cnt<<1|1,tot-tme[cnt]-i));
    return f[cnt][tot];
}
int main()
{
    cin>>t;
    init(1);
    cout<<dfs(1,t-1);
}
论如何枚举所有状态————P1077
本来以为做那么多题能写出来结果还是失败了
就差那么一点啊
再表示一下数量啊喂

int main()
{
	cin>>n>>m;
	for(int i=0;i<=n;i++)f[i][0]=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		for(int j=0;j<=a;j++)
		for(int k=0;k<=m-j;k++)
		{
			if(!j&&!k)continue;
			f[i][j+k]=(f[i-1][k]+f[i][j+k])%mods;
		}
	}
	cout<<f[n][m]%mods;
}