动态规划
超详细背包DP九讲（算法分析+问题分析+代码分析）
P01:01背包问题题目：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
DP优化（三）四边形不等式优化实例讲解
有一种DP可以写成四边形不等式，那么可以用一个优化来优化这种DP（一般是二维的，不加优化是O(n3)）。如果a≤b≤c≤d，那么如果DP式子满足f(a,c)+f(b,d)≤f(b,c)+f(a,d)，那么这就是一个四边形不等式。一、首先先看一道例题题目：有一群人要乘船,
线性DP图文实例讲解
线性DP，所谓线性DP，就是指我们的递归方程有一个明显的线性关系的，有可能是一维线性的，也可能是二维线性的。例题一：大盗阿福题目：阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有NN家店铺，每家店中都有一些现金。
什么是状态压缩DP？
状态压缩DP一般是基于二进制进行的。状态压缩DP一般分为两类：①基于连通性DP（棋盘式）②集合式（表示每一个元素是否在集合中）一、概述1.状态压缩状态压缩就是使用某种方法，简明扼要地以最小代价来表示某种状态，通常是用一串01数字（二进制数）来表示各个点的状态。
状态压缩DP图文实例讲解（二）
本文是讲解状态压缩DP的第二部分，仍然是对基于连通性问题的探讨与学习。一些概念性的问题，以及基本解法在第一节中讲过，这里就不再赘述。对典例蒙德里安的梦想的分析直接看例题：求把N×M的棋盘分割成若干个1×2的长方形，有多少种方案。例如当N=2，M=4时，共有5种方案。
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)的。