洛谷(dp) 动态规划练习的部分题目心得

发布时间 2023-04-05 00:12:18作者: 顾友

P1044 栈这个题目

  • 最大的问题是完全没有想清楚dp数组如何定义,完全陷入了背包的那个dp数组含义中了,导致怎么都想不出关系, 而且看了题解提示之后也无法领悟递推的思想,无法感受那种由前面推导后面的思想.

导弹拦截 P1020

  • 这题是我太惯性思维了,疯狂往如何才能构造dp数组想,然后没能真的把握题目在问什么东西,它第一问是求最长不增序列,第二问是求最大上升序列,我完全没有get到这点,一直在疯狂自己想
  • 后面终于用O(n^2)写出来100分,至于二分的方法,我没想出来,看了题解才知道我哪些细节没有处理好,主要还是对求这题目的两问母题不熟

摆花P1077

  • 这题最开始完全想不到改怎么入手,经过几天的dp练习后感觉自己有感觉了,但是写的时候发现还是搞错了,弄得很复杂,没有想清楚dp数组正确的定义方式
  • 就是状态是什么,状态如何转变,初始状态如何定义这些都需要考虑清楚(如果不是瞄了一眼题解定义dp数组的方式我还是想不出来
  • 我想的是第i种花摆j盆达到k的可能,而别人定义的dp数组是第i种花,刚好到j盆的可能其中k是选第i种花的个数变化范围

P1233

  • 这题我最先想到了排序,后来想到了最长上升子序列,就是没想到过先排序然后只判断一个的最长上升子序列就行了!!!

P2858

  • 这题是区间dp我完全没有该如何分区间的思路,直到看了篇题解,发现里面的思路是 i-j 可以为 i + i+1->j 和 i->j-1 + j 就是头尾选择,这个思路太牛逼了。

P2007

  • 这题我其实最开始想的是模拟,一次性先算一部分,然后再特判,后来发现特判很麻烦,然后死活想不到如何定义dp数组,就选择用贪心暴力写了,最终还是有个点过不了,而看到题解有个思路,是先贪心能回魔就回魔,然后再从头遍历一遍用来找全局最优解这个我是没转过弯来)