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

[sparkyen]

https://wizarderror.github.io/2020/02/18/%E4%B8%93%E9%A2%98%E8%AE%AD%E7%BB%831/

[TheLuckDog]

多写多练习吧，毕竟动态规划是一种思维，思维方式的形成要多实践。 https://blog.csdn.net/weixin_43751631/article/details/104474694

[edisoncgh]

动态规划是很基础的内容，但是深入思考后也能发现很多以前没弄清楚的东西。事实上没有一种算法是浅薄的，还有很长的路要走。 https://www.edisoncgh.com/archives/100

[sparkyen]

害，莫名其妙gitalk挂了 虽然自己以前看过dp，也学过，但是那会就有人面试让我当面敲01背包，我当时愣了，就感觉学过但是敲不出来，所以只能说那会还没有真正掌握，理解他的思想 通过这次主讲，我也把基础的背包的问题再过了一遍，背包九讲给我很多思想上的启发，状态之间的转移和优化都是有其中的道理的。就像楼上说的动态规划是一种思维，将一个复杂问题的背景抽象出状态表示，然后设计他们间的转移。虽然dp有很多种，分别针对不同的问题，但是总的思想还是上句话说的。 尽管会，但是比赛的时候我还是想不出来，去形成这种思维还需要大量的练习，可能我缺的不仅仅的是系统的学习，还有题量的量要够

[Osilly]

黄文轩 这一次dp主要做的和看的是背包问题，以前初看背包许多没搞清楚的问题这一次基本都理解了，比如01背包和完全背包的一维数组优化，还有多重背包的转化方法等等一系列，感觉确实收获良多

[RespectTang]

李蕊芬

第一周总结

1.把寒假训练营的题目补得差不多了，除了第五场的C语言IDE和四场的J题二维跑步以外其他的题目都写了或者过了，目前还剩第五场的街机争霸和第六场的导航系统还没有过，因为搜索的题目个人其实不是很喜欢去写emm

2.复习了暑假的两个题目，第一场的E和H，重新讲解了一遍线性基，因为已经给大家讲了好多遍线性基，所以对与线性基的内容了解的更深了，周五的周赛A题本来很简单，但是因为一开始组合数的式子写错了所以样例推了好久好久也没有推出来正确的答案，考虑到样例是2的幂自己算出来的答案和样例给出的答案差一些，大胆推测wa了两发，因为快速幂的板子没有换成long long，签到题耗了很久很久，B题是哈希求证的题目，在寒假训练营里做了类似的题目，但是代码写出来之后一直有bug结束了也没有调处来，这两道题题意都和组合数有关系，把组合数打表的方法记得很清楚，因为ABBA的题目有用到，果然相比于DP的做法还是更喜欢组合数+线性规划一些

第二周计划

1.花了一晚上做了第二周的计划表，按照小时计算每一个小时安排的明明白白，在网课的基础上每天写一套三级的题目一套四级的题目，看了网课感觉网课没有刷题来的实在一点

2.上网课编译原理和计算机组成结构好好做笔记，虽然这两门课是老师自己让看视频学，但这是考试课所以不得不低头

3.每天晚上帮朋友复习C语言，觉得二级其实挺难的？

4.这周没有学英语的计划，等下一周再安排，这周主要调整的是早睡早起

[Yvonne-sq]

卢思琦： 感觉dp真的挺难想的，有的用的挺巧妙的，感觉想不到，自己感觉懂那么一点，也知道大概怎么做，就是做不对，怎么改也改不对，看了博客之后觉得别人能用简洁并且易懂的代码表达出来，还是差些火候，自己对dp训练的不到位，多想多总结外加多加练习，加强记忆。https://www.cnblogs.com/lusiqi/p/12355120.html.然后学习了线性基，看了看b站，然后听学姐讲了讲，自己也看了很多的博客，对线性基有了一定的理解，并且XOR代码也能完全理解，不过对这一块的练习还没有开始。外加一些小知识点。

[Xu-Luheng]

徐璐衡： 1.这周的比赛完全懵了，一道都不会。差距很大，所以目前先不搞他，先补手头寒假训练营的题目。 2.dp的题目就是很磨脑子，重点就在于找到递推关系，然后用代码表示出来。但有些题目若不说要用dp做完全都想不到需要dp，而且就算找到了递推关系也需要很大功夫才能将想法用代码打出来去实践，一边打代码一边又发现自己的递推关系有地方找得不对。还有dp数组的边界处理也得仔细考虑。需要一边敲，一边修改自己的想法。 3.看了寒假数论讲解的回放，但对知识的了解还是不系统，不知道该怎么用。 4.作息调过来了超愉快，游戏也卸了。我终于不是一天20小时窝床上的抱窝老母鸡了 5.C++正式学着有点难，想要拥有课本。

[aminoed]

李卓

专题总结

1.回归牛客的比赛果然是让人头秃。一上来就看B，一发快速幂加逆元打表就想过，数据却在20多秒的时候拦住了我。(过于小看牛客测评机)

2.专题训练让我感觉可以很系统的了解一个方面的知识点，就很棒。dp在我的印象中一直最难的就是找到递推关系，我一般简单的就直接推数学通式，难的就直接看不出来,所以自己用的就很少。缺少题目的锻炼和比赛时的灵感。学姐周六讲的xor让我捡起了暑期对线性基的回忆，感觉比第一次听起来好多了😂。这星期主要在写Java高级的界面，学HTML和CSS去了，博客会补起来的(适时的给自己挖了一个坑)

总结：知识果然是长学长新，每次都有新感觉

[hyb1041739742]

黄勇斌：

感觉动态规划的思想有一点了，但是大多数自己想还是弄不出来，但是看了别人的博客还是可以看懂， 我觉得自己在接下来的日子还是在这方面还是要多加练习。

[LJR233]

刘金瑞： 看了一点背包九讲，然后听了学长的讲解感觉有那么一种思想了，但是自己还确少代码的练习与实践，接下来要找博客看然后做题

[Baby-Whale]

张怡： 1.这周的比赛做了两道签到题就没了，挑战赛的难度还是蛮大的，没有补训练营的题目，比较懒（捂嘴）。 2.还打了一场小白月赛，难度小一点，但是感觉做的一般，三道签到题，然后做了一道关于STL运用的题A题，感觉还不错，是map+set(堆）的运用，也是想了半天。 3.dp的题目本来就比较难想，但是看了别人思路又恍然大悟，所以独立思考dp的转换关系就比较重要，专题很好 4.最近几天比较懒散，还错过了一次讲题，以后要规律一下作息 5.还要好好准备一下美赛，学习和回顾一下模型，自己比较菜，什么都不懂，要学的还有很多

[qiyuan11111]

郑依鸣： 1.这周牛客挑战赛终于上了分，虽然只做了两道签到题，后面的题目看了一眼，感觉逻辑甚是有趣，特别是最后一道题非常创新，很像牛客暑假走圈圈的题目但是也不是递推关系，后来想到了容斥定理但是不知道怎么来容斥，然后就GG了。 2.oj搞好了，准备进行二次开发，目前刚刚加了题目多组样例数据的功能，但是oj前端还是很丑请大家稍等。 3.dp的话这几次dp的题目逻辑还是被找出来了（相比我进acm那个传球的招新题，现在感觉变简单了），dp的训练永无止境。 4.四级过了，慢慢背六级单词和准备计算机四级

[Stone-pl]

DP的推算公式太难想了，需要灵感，感觉DP应该是一种思想，要多做才能发散思维，XOR的代码看别人的代码看懂了，自己敲得话应该是不行的，DP和别的内容糅杂起来就更不好做了。 接下来一段时间还是以DP为主把，多做些这类的题，眼前主要的还是蓝桥杯省赛

[Amaranth-zf]

这一周的比赛标签就让我很慌，之前做难度《偏低》都只能做下签到题。果不其然，爆0了。但是听讲题收获还是很多的：大数取模、关于题目信息对复杂度的猜测....我感觉和学长学姐统一内容学习的确有难度，可能要先把题目知识点先完全搞清楚，再自己独立补出来，所以进度会很慢。至于DP，的确需要有一种思维的跳跃，想出来了如何dp可能还要根据题意进行优化。dp的解题的确有一点玄学，多做多听多见识叭。

[sparkyen]

马程栋 不知道什么原因，家里的网变得很差，然后本周牛客的题我看了看，A题没理解题意，B题有思路但是很暴力，后面的题没太看懂，就提交也提交不了，现在流量也限速了，所以最近就很水，本周的任务是DP，之前有一点点的基础，用QQ电话讲知识点的时候就一卡一卡的，所以主要还是自己在看一些博客，感觉还算有点长进。现在就很多网站也打不开，表示很抱歉。

[kkk-x]

孔维暄 dp的规律还是很难找，自己写很久思路还是会感觉很乱，规律也似有似无的找不清楚，一些小点可能是解题关键，但自己可能想不通，看了题解博客又有了一点点感觉，但自己做题时还是想不到解题方法，得多加练习，在做背包的题之前，翻看了一下之前的代码，时间一长，突然翻开看感觉还得理解一下才能想通之前的思路，果然自己的代码过一段时间可能还是会看不懂，以后要记得给自己加注释 对于线性基在之后需要再学习学习，再理解理解，感觉还是很懵，知识点没有串起来

[yihaibin1]

易海斌 我觉得dp还是比较难把握的，一难在关系式的推到，二难在dp数组维度的确定，三难在变量含义的把握，每次看到dp新题的时候都有点蒙，自己还是练习少了，要多加练习

[sparkyen]

易海斌 我觉得dp还是比较难把握的，一难在关系式的推到，二难在dp数组维度的确定，三难在变量含义的把握，每次看到dp新题的时候都有点蒙，自己还是练习少了，要多加练习

dp数组维度其实不是很难确定，一般是题目卡空间不让过，必须要用滚动数组优化时才去降维

[jin-feng]

刘锦锋 自己重新温习了背包问题，然后看了背包九讲的视频，自己看的时候的那个状态压缩，把二维压缩成一维，刚开始没看懂，讲了后就懂了，觉得很有意思。这个背包九讲感觉还是很有用的，不过相应的练习还是没做到位，需要开始刷题补题了。

[backdiy]

dp之前有看过不少，但是用起来还是不够熟练。这次周任务有重新再看dp，刚开始的时候背包差点忘了，但慢慢的找到了之前的感觉，看背包九讲的时候也收获很多新的，以前没有看过的内容。之后还是多做题吧，另一些常用的dp也要学会