动态规划

1. Dotcpp
2. 动态规划

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

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

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

区间DP实例讲解一、什么是区间DP?顾名思义：区间DP就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的DP算法。二、核心思路既然让我求解在一个区间上的最优解，……

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

状态压缩DP图文实例讲解（二）本文是讲解状态压缩DP的第二部分，仍然是对基于连通性问题的探讨与学习。一些概念性的问题，以及基本解法在第一节中讲过，这里就不再赘述。对典例蒙德里安的梦想的分析直接看例题：求把N×M的棋盘分……

什么是状态压缩DP？状态压缩DP一般是基于二进制进行的。状态压缩DP一般分为两类：①基于连通性DP（棋盘式）②集合式（表示每一个元素是否在集合中）一、概述1.状态压缩状态压缩就是使用某种方法，简明扼要地以最小代价来表示某……

记忆化搜索实例讲解什么是记忆化搜索？记忆化搜索在本质上，还是动态规划，只是实现方式采用了深度优先搜索的形式，但是它不像深度优先搜索那样重复枚举所有情况，而是把已经计算的子问题保存下来，这样就和动态规划的思想不谋而合了。……

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

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