动态规划

1. Dotcpp
2. 动态规划

动态DP实例讲解一、简介有一类问题，它可以采用DP解决。但是，如果我们加入区间查询，单点修改甚至区间修改，普通DP望尘莫及。于是，动态DP就应运而生了。二、例题例题一：给定一个长度为n的序列，你需要维护两种操作：①查……

DP优化（一）单调队列/单调栈优化实例讲解一、什么是单调栈和单调队列？（1）单调栈从名字上就听的出来，单调栈中存放的数据应该是严格单调有序的，具有以下两个性质。1.满足从栈顶到栈底的元素具有严格的单调递增或单调递减性；2.满足栈的后进先出特性……

DP优化（二）斜率优化实例讲解有一类DP状态方程，例如：dp[i]=min{dp[j]−a[i]∗d[j]}  0≤j<i,d[j]≤d[j+1],a[i]&……

DP优化（三）四边形不等式优化实例讲解有一种DP可以写成四边形不等式，那么可以用一个优化来优化这种DP（一般是二维的，不加优化是O(n3)）。如果a≤b≤c≤d，那么如果DP式子满足f(a,c)+f(b,d)≤f(……