算法与数据结构-入门打卡帖

开一个UCSD 的算法打卡贴，准备上完整个specialization，占坑后补内容。 楼主因为工作需求和职业发展原因学习算法
已经完成了algorithms toolbox (1/6), 现在在学data structure。 第一门课在最后两周陆续有两道题做不出来了，之后复习希望能搞定，如果有这门课刷到100%的大神也求一发高质量的讨论。

感觉写过作业很容易忘记，而且囫囵吞枣写过感觉并没有学到精髓。举个例子，自己复习的时候发现一道经典题目的edge case并不能跑过，但是coursera并没有检查出来就过了。所以复习整理代码的时候还会贴一些心得笔记。

有一起上课的欢迎一起打卡！

打卡一个longest common sequence 问题。求算三个list的longest common sequence长度。以下简称LCS.

1. Dynamic Programming 问题
2. 是2D问题的generalization
3. 本质上与课堂举例editing distance问题相似，只是我们只在乎match情况：只有A[i] = B[j] = C[k]的时候match数会+=1
4. 综合1，2，3， 问题的重点是寻找i,j,k同i-1,j-1,k-1之间的“recurrence”关系。而这个关系是：
- 当 A[i] = B[j] = C[k]: match +=1
- 当以上关系不成立，我们取临近（一个修改距离）LCS的最大值。

MadLily 发表于 2018-8-13 11:47
打卡一个longest common sequence 问题。求算三个list的longest common sequence长度。以下简称LCS.

1.  ...

下一个应该会回顾Dynanmic Programming I 的第二题，因为第一次做的时候时间没过，后来做了几个版本。之后会回顾一下Week6 Dynamic Programming II 的课本题目（Q1, Q3).. Q2 还不会做吖。。