练习1：编辑距离 Luogu P2758

状态：\(f[i][j]\)：字符串 \(A\) 的前 \(i\) 个字符变为字符串 \(B\) 的前 \(j\) 个需要的最少步数

状态转移：
\(delete:f[i][j]=min(f[i][j],f[i-1][j]+1);\)
\(input:f[i][j]=min(f[i][j],f[i][j-1]+1);\)
\(change:f[i][j]=min(f[i][j],f[i-1][j-1]+1);\)
\(none:f[i][j]=min(f[i][j],f[i-1][j-1]);\)

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        f[i][j]=INF;
for(int i=0;i<=n;i++)
    f[i][0]=i;
for(int i=0;i<=m;i++)
    f[0][i]=i;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        //delete  ABCD ABC
        f[i][j]=min(f[i][j],f[i-1][j]+1);
        //input  ABC ABCD
        f[i][j]=min(f[i][j],f[i][j-1]+1);
        //change  ABCE ABCD
        if(s1[i]!=s2[j]) f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        //none  ABCD ABCD
        else f[i][j]=min(f[i][j],f[i-1][j-1]);
    }
}
cout<<f[n][m]<<endl;

练习2：交错匹配

有两行自然数，\(up[1 \sim n]\)，\(down[1 \sim n]\)，如果 \(up[i]=down[j]=k\)，

那么上行的第 \(i\) 个位置的数就可以跟下行的第 \(j\) 个位置的数连一条线，称为一条 \(K\) 匹配，

但是同一个位置的数最多只能连一条线。

另外，每个 \(k\) 匹配都必须且至多跟一个 \(l\) 匹配相交且 \(k \neq l\) 。现在要求一个最大的匹配数。

例如：以下两行数的最大匹配数为 \(8\)

（七）二维动态规划

例题1：过河卒 Luogu P1002 [NOIP2002 普及组]

用 \(vis\) 数组标记马能到达的坐标

状态：\(f[i][j]\)：到达点 \((i,j)\) 的路径数目

状态转移：\(f[i][j]=f[i-1][j]+f[i][j-1]\)

for(int i=0;i<=yb;i++)
    if(vis[0][i]) break;
	else f[0][i]=1;
for(int i=0;i<=xb;i++)
    if(vis[i][0]) break;
	else f[i][0]=1;
for(int i=1;i<=xb;i++)
{
    for(int j=1;j<=yb;j++)
    {
        if(vis[i][j]) f[i][j]=0;
        else f[i][j]=f[i-1][j]+f[i][j-1];
    }
}
printf("%d\n",f[xb][yb]);

例题2：传纸条 Luogu P1006 [NOIP2008 提高组]

状态：\(f[i][j][k][l]\)：第一个纸条传到了 \((i,j)\)，第二个纸条传到了 \((k,l)\) 的时候能获得的最优值

我们发现，四维状态会枚举许多不会出现的状态

当两个纸条同步的时候，在某个时间，他们所处的两个位置行列之和是相等的

因为他们走的步数是一样的，由此，得到如下状态：

状态：\(f[p][i][j]\)：当前走了 \(p\) 步，第一个个人走到第 \(i\) 行，第二个人走到第 \(j\) 行的最大价值

状态转移：

for(int k=1;k<=m+n-1;k++)
{
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            if(i>k||j>k) continue;
            f[k][i][j]=max(max(f[k-1][i][j],f[k-1][i-1][j]),max(f[k-1][i][j-1],f[k-1][i-1][j-1]))+a[i][k-(i-1)]+a[j][k-(j-1)];			
        }
    }
}
printf("%d\n",max(f[n+m-1][m][m-1],f[n+m-1][m-1][m]));

例题3：农田个数

你的老家在农村。过年时，你回老家去拜年。

你家有一片 \(N \times M\) 农田，将其看成一个 \(N \times M\) 的方格矩阵，有些方格是一片水域。

你的农村伯伯听说你是学计算机的，给你出了一道题：

他问你：这片农田总共包含了多少个不存在水域的正方形农田。

两个正方形农田不同必须至少包含下面的两个条件中的一条：

1. 边长不相等
2. 左上角的方格不是同一方格

状态：\(f[i][j]\)：以方格 \((i,j)\) 为右下角，可以得到的最大无正方形边长

状态：\(f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1\)

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if(a[i][j]==0) f[i][j]=0;
        else f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+1;
        ans+=f[i][j];
    }
}
printf("%d\n",ans);

练习1：矩阵切割

给你一个矩阵，其边长均为整数。

你想把矩阵切割成总数最少的正方形，其边长也为整数。

切割工作由一台切割机器完成，

它能沿平行于矩形任一边的方向，从一边开始一直切割到另一边。

对得到的矩形再分别进行切割。

练习2：创意吃鱼法 Luogu P1736

练习3：方格取数 Luogu P1004 [NOIP2000 提高组]

练习4：方格取数 Luogu P7074 [CSP-J2020]

练习5：滑雪 Luogu P1434 [SHOI2002]