苏庆栋

题解

/ 注册

全部文章 / 题解（共3篇）

题解 | #合唱队形#

思路关于怎么理解“峰型”队形：以160,170,155,180,170,160为例。对于其中的每个人，我们求两个值，分别设dp1[6] 与dp2[6] 其中dp1[i] 意为从0开始到i为止这前几个人的最长上升子序列长度。如，对于180的人而言，dp1[3] = 3 (也就是 160,1...

C++ 动态规划

2022-02-15

6 539

题解 | #拦截导弹#

第一问没什么说的，跟DP9 一样，就是改成了下降序列。第二问求个数，由于没思路，查题解查到了一个Dilworth定理偏序集能划分成的最少的全序集个数等于最大反链的元素个数。查到的一个比较好的博客对本题，第二问就是求该序列“严格上升子序列最大长度”，这个数就等于所求的下降序列个数 #incl...

C++ 动态规划

2022-02-14

2 597

题解 | #最小花费爬楼梯#

DP问题五步走： dp数组的含义以及下标的含义递推公式如何初始化遍历顺序打印数组本题对前四个问题有着非常好的示范效果。题目分析在代码里解释的应该比较详细了，不再赘述。吐槽一下测试用例有六次方，题目里说了到五次方。第一篇牛客题解，溜了溜了 #include<iostream&...

C++ 记忆化搜索动态规划

2022-02-12

4 514