数位DP概念和实例讲解
说到数位DP，它主要是用于处理一些与数位有关的问题，主要是计数问题。并且数位DP一直以来是DP家族里比较冷门的一种，但一旦遇上了，如果不会数位DP单纯靠暴力方法很难骗分。一、什么是数位DP？数位DP是一种计数用的DP，一般就是要统计一个区间[l,r]内满足一些条件数的个数。
动态规划
树形DP概念和实例讲解
一、什么是树型动态规划顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：（1）叶－>根：在回溯的时候从叶子节点往
动态规划概念和实例讲解
动态规划（Dynamicprogramming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
DP优化（二）斜率优化实例讲解
有一类DP状态方程，例如：dp[i]=min{dp[j]−a[i]∗d[j]} 0≤j<i,d[j]≤d[j+1],a[i]≤a[i+1]它的特征是存在一个既有i又有j的项a[i]∗d[j]。编程时，如果简单地对i和j循环，复杂度是O(n2)的。
什么是状态压缩DP？
状态压缩DP一般是基于二进制进行的。状态压缩DP一般分为两类：①基于连通性DP（棋盘式）②集合式（表示每一个元素是否在集合中）一、概述1.状态压缩状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。
DP优化（三）四边形不等式优化实例讲解
有一种DP可以写成四边形不等式，那么可以用一个优化来优化这种DP（一般是二维的，不加优化是O(n3)）。如果a≤b≤c≤d，那么如果DP式子满足f(a,c)+f(b,d)≤f(b,c)+f(a,d)，那么这就是一个四边形不等式。一、首先先看一道例题题目：有一群人要乘船,
状态压缩DP图文实例讲解（一）
动态规划算法的过程是随着阶段的增长，在每个状态维度上的分界点组成了DP拓展的轮廓。对于某些问题，我们需要在动态规划的状态中记录一个集合，保存这个轮廓的详细信息，以便于进行状态转移。若集合大小不超过N，集合中每个元素都是小于k的自然数，则我们可以把这个集合看做一个N位k进制数，