$DP$

Note

区间$DP$

例题1

首先你有M个矩阵大小分别为
$[N_{0}\times N{1}] , [N_{1}\times N_{2}]...[N_{M - 1}\times N_{M}]$，要求你求出这些矩阵乘积的最小次数。

我们设$F[L][R]$为第L个矩阵和第R个矩阵的乘积所需要的最小的代价。那么我们知道当我们计算$F[L][R]$的时候我们中间一定有一个断点$K$，然后将整个$[L,R]$区间分为$[L, K]$和$[K + 1, R]$，然后我们相加就是答案之一，然后我们还要计算所有东西相乘所要求的代价，而矩阵的相乘起来的列数和行数也就是最左边的列数和最右边的行数。那么代价就是$N_[L - 1]\times N_[K]\times N_{R}$。那么我们得到了状态转移方程式。
$F[L][R] = min_{L <= K <= R}(F[L][K] + F[K + 1][R]) + N_[L - 1]\times N_[K]\times N_{R}$

但是要注意代码不可以这么书写：

for(int L = 1; L <= N; L ++)
    for(int R = L; R <= N; R ++)
        for(int K = L; k <= R; K ++)
            F[L][R] = ......

在这种代码里面$L$是从小到大枚举的。那么当你枚举$L$的时候，任何以比$L$大的数为左端点的$F$都没有求出。所以$F[K + 1][R]$是没有求出的。所以这种求法是错误的。然后我们应该在最外面枚举区间长度，里面枚举端点，在里面枚举$K$。

for(int Len = 2; Len <= N; Len ++)
    for(int L = 0, R = L + Len; L <= N, R <= N; L ++, R ++)
        for(int K = L; K <= R; K ++)
            F[L][R] = ......

树形$DP$

你现在有一个

数位$DP$

状压$DP$

现在有N个点的坐标分别为$(X_{1}, Y_{1}), (X_{2}, X{2})...(X_{N}, Y_{N})$要求从$1$号点出发了，走完所有的点的最小距离为多少。

我们设$F[i][j]$表示走过了i这个集合的所有的点并且最后停在j号点的最小距离。换句话说，我们用一个$01$串表示状态，对于每一个$i$点，如果这个串是$1$表示走了，反之没走。那么$F[i][j]$表示从1走到j并且状态为$i$的最小距离。那么我们就可以实现状态转移了。