[数据结构与算法]2021-08-19

1.最长括号匹配：显然是一个线性动态规划，有点像LIS(最长不下降子序列)。可以容易想到，用f[i]表示以i结尾的最长子串。只有当str[i]==')'||str[i]==']'有意义。

????????考虑如何转移，我们可以分为两种情况，①[()]，嵌套式，②()[][]()并列式。当然，还有混合式的，对于第一种，我们需要对']'匹配'['，并把中间的和该子串之前的加上，'['之前还可能有东西。显然，可以发现，'['对应的位置是i-1-f[i-1],因此得到状态转移方程：f[i]=f[i-2-f[i-1]]+2+f[i-1];

2.线性生物：期望dp,这道题有点类似解方程的思想，状态设计和转移也比较清楚，很不错的概率题

3.货币系统：有两个重要的结论：①B一定包含于A集合②如果由已选的数能组成当前的数，当前的数就没有必要选。因此，我们可以先sort一下，看看每个数是否能被合成，然后这道题就变成了一个完全背包