区间dp问题 浅浅的花香味﹌ 2022-09-12 12:54 175阅读 0赞 区间dp一般有以下几种类型的题目: * 如何将环形区间问题转换为线性dp问题 * 如何记录方案数目 * 区间dp与高精度的结合 * 高维区间dp问题 一般区间dp有两种实现方式:① 迭代式(一般维数比较少的的时候比较好写一点),迭代式的写法都是有固定套路的,一般至少使用三层循环枚举,第一层循环枚举区间长度,第二层循环枚举区间起点,第三层循环枚举当前区间的分割点代表的集合,求解当前起点为i,终点为j的区间最值 ② 记忆化搜索,记忆化搜索适合于维度比较高的区间dp问题,在方法中传递需要的参数即可,代码比较容易编写。迭代式区间dp写法: for(int len = 1; len <= n; len++){ for(int l = 1; l + len - 1 <= n; ++l){ for.... } } 可以发现大部分区间dp的问题一般与"**划分**"有关或者只能够对**相邻位置的元素进行操作**的问题,根据某个策略进行划分,划分之后的**每一部分是相互独立**的,要想使得整个集合求得最值,那么应该使每一部分求解出最值,那么就可以得到整个集合的最值。
还没有评论,来说两句吧...