动态规划
树形DP概念和实例讲解
一、什么是树型动态规划顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：（1）叶－>根：在回溯的时候从叶子节点往
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)的。
动态规划概念和实例讲解
动态规划（Dynamicprogramming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
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知识，以及前置知识：哈希，方便大家能快速理解。在阐述什么是插头DP之前，我们先了解插头DP有什么用？插头DP是用来解决一类网格图上的连通性问题的强力工具。题目的特征是给定的网格非常小（这个特征类似状压DP）。