数字三角形

顺推法

由左上方和上方的和
f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);

逆推法

下方和右下方的值
f[i][j]+=max(f[i+1][j],f[i+1][j+1])+a[i][j]

最长上升子序列

计算n*i次循环
最极端的情况长度为 $1$
f[i]=max(f[i],f[j]+1)

最长公共子序列模型

还是第一次接触字符串类的 $dp$

分成 $4$ 类

不选a[i]不选b[j]的是f[i-1][j-1]
不选a[i]选b[j]:f[i-1][j]
选a[i]不选b[j]:f[i][j-1]
两个都选,f[i-1][j-1]+1
四种的最大值
最后就是答案

编辑距离

删除

删除后a[i]~b[j]匹配,删除前a[i-1]~b[j]匹配,f[i-1][j]+1

增添

增添前a[i-1]~b[j]匹配,插入之后保证匹配f[i][j-1]+1

替换

替换前a[i-1]~b[j]匹配,替换之后匹配f[i-1][j-1]+1
如果已经一样就加 $0$