DP优化（三）四边形不等式优化实例讲解
有一种DP可以写成四边形不等式，那么可以用一个优化来优化这种DP（一般是二维的，不加优化是O(n3)）。如果a≤b≤c≤d，那么如果DP式子满足f(a,c)+f(b,d)≤f(b,c)+f(a,d)，那么这就是一个四边形不等式。一、首先先看一道例题题目：有一群人要乘船,
算法
简单选择排序算法实例详解
1.复杂度与稳定性算法时间复杂度最坏情况：O(n^2)最好情况：O(1)//即不需要排序，本身已是正序平均情况：O(n^2)空间复杂度：S(n)=O(1)稳定性：不稳定排序2.过程介绍（以顺序为例）1.我们设置两个记录i和j，i自数组第一个元素开始，j自i+1个元素开始。
KMP算法与前缀函数实例讲解
KMP算法与前缀函数（一）前缀函数一个字符串s的border是一个最长的字符串，且既是s的后缀，又是s的真前缀。给定长为n的字符串s，其前缀函数定义为一个长为n的数组π。其中π[i]为s的第i个前缀的border长度。（二）KMP算法全称为Knuth-Morris-Pratt算法，
归并排序算法实例详解
1.复杂度与稳定性算法时间复杂度最坏情况O(NlogN)最好情况O(NlogN)平均情况O(NlogN)空间复杂度O(N)注：归并排序需要创建一个与原数组相同长度的数组来辅助排序稳定性：稳定排序2.过程介绍归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列。
线性DP图文实例讲解
线性DP，所谓线性DP，就是指我们的递归方程有一个明显的线性关系的，有可能是一维线性的，也可能是二维线性的。例题一：大盗阿福题目：阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有NN家店铺，每家店中都有一些现金。