#题目描述
#做法
\[f_{i,j,k}=\left\{\begin{array}{ll} f_{i-1,j,k} & \mathrm{所有情况}\\ f_{i,j-1,k} & \mathrm{所有情况}\\ f_{i-1,j-1,k} & \mathrm{所有情况}\\ f_{i-1,j-1,k}+1 & x_i=y_i\\ f_{i-1,j-1,k-1}+1 & x_i=y_i=z_i \end{array}\right.\]其实第二种情况是多余的
很简单吧,就是在普通的LCS上加上一维
注意要有滚动数组哦~
#复杂度分析
时间\(O(N^3)\)
空间\(O(N^2)\),其实可以卡到\(O(N)\),但是那样蛋会疼
#AC Code