【专题训练】基础dp(下) - CTGU ACM

[sparkyen]

https://ctguacm.work/2020/02/23/%E4%B8%93%E9%A2%98%E8%AE%AD%E7%BB%832/

[TheLuckDog]

Lis和Lcs都是原本比较熟悉的算法。后面区间dp的题目，不是很熟悉，去了解了一些(不是很深入，四边形优化有点了解，还没用来写过代码），最难受的是第三题，区间dp搞不定(虽然看题意是模板题，实际上要用GarsiaWachs算法),GarsiaWachs算法算法我的意义我清楚，又说不明白。有点难受说实话。 博客还是贴一下(毕竟写了几个小时)： https://blog.csdn.net/weixin_43751631/article/details/104531104

[sparkyen]

肖焰 这是算是我第二次看论文吧
其实出专题训练从某种方面来说也是检验自己检验到底这些学的怎么样，是不是真的会。LIS因为上次写过了精灵宝可梦那题，所以就直接想了想敲出来过了，但是LCS就只把状态给定义出来，之间的转移设计的有问题，最后想不出来看的题解，还很理解了一会儿 。
那道POJ的石子合并是我故意那样出的，的确不是用区间dp解决的，意在告诉你dp是可以一步步优化的。然后四边形不等式的论文我看了一晚上，真的很难懂，最后只是看个大概，其实还是水过去了。
括号匹配的话我是真的觉得网上很多人在口胡，也可能别人都知道懒得说了。是今天早上我才想到为什么要那样转移，只有那两张方式是合法的，所以才有那两种转移形式，还是要好好看题意

[Yvonne-sq]

卢思琦： 这又是一个dp专题，感觉多dp的了解更多了，不过还是有的不是很理解，An old Stone Game里面要用到的GarsiaWachs算法还不是很懂，他的证明感觉有些深奥了，然后用结论写代码的话感觉也是很困难，看了代码也不咋懂，dfs里面再dfs，同时变量很多，而且经常改变，还在下一个dfs里面用到，根本的东西实在不咋懂，准备先放一放，学的东西多了，可能就会明白更多。https://www.cnblogs.com/lusiqi/p/12374472.html

[aminoed]

李卓

这周讲的LIS和LCS之前就做过，肖焰讲的又很清楚，以后这种应该就没问题了吧😂后面讲了区间dp，之前没怎么接触过，感觉思想有点像分治。取石子学的GarsiaWachs算法还挺神奇，讲完又看了下博客就明白了些。最后讲的四边形不等式优化可能还要再理解一下才行，DP总算是入了门，难点就在状态转移方程，期待下周数论大佬的讲解

[jin-feng]

刘锦锋： 这次的dp收获最大的就是区间dp了，组长讲的那道牛客的dp思想的题，感觉很综合，第n个状态需要1到n-1这个区间进行转移，思想是好懂的，但是实际操作还是有些问题。然后取石子的题，看网上的博客的话还是有些不懂得，听过讲解后还是需要自己去思考才能有所收获。最后的四边形不等式优化是没整明白的，还得继续加油学习。

[kkk-x]

孔维暄 感觉LIS和LCS还是比较容易理解的，代码也比较简单，虽然还是没忍住先看了题解，刚看完题解代码敲得比较顺，思路也比较清晰，但是刚刚又自己尝试敲了一遍发现会有一些循环条件出现小问题，石子和括号的题就不太容易了，因为没有提前做，只是大概看了一下题目，讲题的时候理解起来就有点吃力，下次周任务一定要提前做好，这周还是很懒，没有写博客，下周改变一下写道自己感受比较深的详解

[Stone-pl]

彭磊 上周很多课都已经开课了，加上自己有一些懈怠，就只做了两道题，算是回顾了一下dp的相关知识把，练了一下手，剩下的两题安排这周的时间补上。要合理做好时间的规划

[Baby-Whale]

张怡 这几天看网课，加准备美赛，周任务没做完，就做了基础的两题，这几天就放一放，比赛过后再认真补题吧，说来惭愧。后面还是脚踏实地认真学，对于基础还不稳的我，基础都还没有掌握，高深的算法又不会，只能打打基础了，脚踏实地最重要！！

[edisoncgh]

陈冠华

专题博客 在任何版本的算法教程里都会告诉你“DP是一种不能再基础的算法”，但这并不意味着它就简单肤浅，事实上它的复杂与庞大在茫茫多的算法中都是首屈一指，与它打了那么多年交道，真正完全理解的DP题型可能不过一手之数。它就像是一本自有黄金屋的好书，每次细究都能有新的收获。这几日碍于暴增的网课数量与作业，没有时间完成所有的专题题目，日后会仔细的全部重做一遍。算法是一门马虎不得浮躁不得的学问。