动态规划

1. Dotcpp
2. 动态规划

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

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

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

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

线性DP图文实例讲解线性DP，所谓线性DP，就是指我们的递归方程有一个明显的线性关系的，有可能是一维线性的，也可能是二维线性的。例题一：大盗阿福题目：阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺……

什么是线性DP?一、什么是线性?越是基础的概念，越应该有一个透彻的理解，才能对上层问题有直接了当的理解。比如对线性分割器，你对线性有透彻的理解，一看这个名字就大概知道它是怎么回事了。1.几何理解：线性关系就是直线关系……

概率DP实例讲解在动态规划中，概率DP一般会用于研究有关于概率，步数，期望等问题。简单总结为以下四个点：（1）数学期望P=Σ每一种状态*对应的概率。（2）因为不可能枚举完所有的状态，有时也不可能枚举完，比……

什么是概率DP？一、概率DP顾名思义，概率DP就是动态规划求概率的问题。一般来说，我们将dp数组存放的数据定义为到达此状态的概率，那么我们初值设置就是所有初始状态概率为1，最终答案就是终末状态dp值了。我们在进行状态……

计数DP实例讲解本篇主要从计数DP上结合实例分析。一、计数类DP——整数划分整数划分大体上可以分为3类（1）考虑顺序的拆分方案（即1，1，2；和2，1，1是两种不同的方案），这种问题一般转化为……

插头DP图文实例讲解本篇通过图文解析讲述插头DP的内容，结合前面的状态压缩DP知识，以及前置知识：哈希，方便大家能快速理解。在阐述什么是插头DP之前，我们先了解插头DP有什么用？插头DP是用来解决一类网格图上的连通性问题……