DP

这个部分其实主要是做一些模板题来积累 \(DP\) 状态设计的经验，以下仅简单记录课上的一些案例。

案例

矩阵乘法次序决定

按照怎样的顺序进行结合才能使最后做乘法的总次数最小化。

记录 f[l][r] 为完成 l 到 r 的乘法的最小次数，则

\[ f[l][r] = \min_{k\in[l,r-1]} f[l][k]+f[k+1][r]+Row[l]*Col[k]*Col[r] \]

卡特兰数相关

• 对应的实例：

  • 矩阵乘法的方案数

  • 出栈次序

  • 括号匹配

其递推公式为 $$ b_n=\sum_{i=1}^{n-1} b_ib_{n-i} $$

通项公式 $$ h_n=\frac{1}{n+1}(_n^{2n}) $$

BST建立

对于这样的单词列表及相应词频

break	case	char	do	return	switch	void
0.22	0.18	0.20	0.05	0.25	0.02	0.08

建立 BST 使得 \(\sum prob_i\times (h_i+1)\) 最小

记 \(f_{i,j}\) 为 i 到 j 区间二叉树建好后的代价 $$ f_{i,j} = \min_{k\in[i+1,j-1]} f_{i,k-1} + f_{k+1,j} + w_{i,j} $$

Floyd

是一种求全源最短路的算法，也许fds有所涉及？

以下是粗略的架构，所有的细节都没有涉及因此可能存在一点小毛病。

Code

Init();
for(int k = 1; k <= n; ++k){
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            f[i][j] = min{f[i][j], f[i][k]+f[k]};
        }
    }
}