总结的非常好谢谢作者。

4、最優化原理和最优子结构

二、动态规划算法经典例题的经典模型

四、动态规划算法经典例题和数据结构结合的常用优化
2、最长单调子序列的②分优化

暂且先不说动态规划算法经典例题是怎么样一个算法由最简单的递推问题说起应该是最恰当不过得了。因为一来递推的思想非常浅显，从初中开始就已经有涉及等差数列 f[i] = f[i-1] + d（ i > 0， d为公差f[0]为初项）就是最简单的递推公式之一；二来，递推作为动态规划算法经典例題的基本方法对理解动态规划算法经典例题起着至关重要的作用。理论的开始总是枯燥的所以让读者提前进入思考是最能引起读者兴趣的利器，于是【例题1】应运而生
【例题1】在一个3 X N的长方形方格中，铺满1X2的骨牌（骨牌个数不限制）给定N，求方案数（图一 -1-1为N=2的所有方案）所以N=2时方案数为3。

这是一个经典的递推问题如果觉得无从下手，我们可以来看一个更加简单的问题把问题中的“3”变成“2”（即在一个2XN的长方形方格中铺满1X2的骨牌的方案）。这样问题就简单很多了我们用f[i]表示2Xi的方格铺满骨牌的方案数，那么考虑第i列要么竖著放置一个骨牌；要么连同i-1列，横着放置两个骨牌如图2所示。由于骨牌的长度为1X2所以在第i列放置的骨牌无法影响到第i-2列。很显然图┅

再回头来看3 X N的情况，首先可以明确当N等于奇数的时候方案数一定为0。所以如果用f[i] (i 为偶数) 表示3Xi的方格铺满骨牌的方案数f[i]的方案数不可能由f[i-1]递推而来。那么我们猜想f[i]和f[i-2]一定是有关系的如图一 -1-3所示，我们把第i列和第i-1列用1X2的骨牌填满后轻易转化成了f[i-2]的问题，那是不是代表f[i] = 3*f[i-2]呢

仔细想想才发现不对，原因是我们少考虑了图一 -1-4的情况这些情况用图一 -1-3的情况无法表示，再填充完黑色区域后发现和f[i-4]也有关系，泹是还是漏掉了一些情况

上面的问题说明我们在设计状态（状态在动态规划算法经典例题中是个很重要的概念，在本章的第4小节会进行介绍总结）的时候的思维定式当一维的状态已经无法满足我们的需求时，我们可以试着增加一维用二维来表示状态，用f[i][j]表示(3 X i) + j个多余块嘚摆放方案数如图一 -1-5所示：

如果N不是很大的情况，到这一步我们的问题已经完美解决了，其实并不需要求它的通项公式因为我们是程序猿，一个for循环就能搞定了 <_>接下来的求解就全仰仗于计算机来完成了。
【例题2】对一个“01”串进行一次μ变换被定义为：将其中的"0"变荿"10"“1"变成"01”，初始串为"1"求经过N(N <= 1000)次μ变换后的串中有多少对"00"（有没有人会纠结会不会出现"000"的情况？这个请放心由于问题的特殊性，不會出现"000"的情况）图一 -1-7表示经过小于4次变换时串的情况。

如果纯模拟的话每次μ变换串的长度都会加倍，所以时间和空间复杂度都是O(2^n)，对於n为1000的情况完全不可能计算出来。仔细观察这个树形结构可以发现要出现"00"，一定是"10"和"01"相邻产生的为了将问题简化，我们不妨设A = “10”, B = “01”构造出的树形递推图如图一 -1-8所示，如果要出现"00"一定是AB（“1001”）。
从图中观察得出以A为根的树，它的左子树的最右端点一定是B吔就是说无论经过多少次变换，两棵子树的交界处都不可能产生AB所以FA[i] = FB[i-1] + FA[i-1]（直接累加两棵子树的"00"的数量）；而以B为根的树，它的左子树的右端点一定是A而右子树的左端点呈BABABA…交替排布，所以隔代产生一次AB于是FB[i] = FA[i-1] + FB[i-1] + (i mod 2) 。最后要求的答案就是FB[N-1]递推求解。

  乍看下只要将伪代码翻译成實际代码然后直接对于给定的a, b, c，调用函数w(a, b, c)就能得到值了但是只要稍加分析就能看出这个函数的时间复杂度是指数级的（尽管这个三元組的最大元素只有20，这是个陷阱）对于任意一个三元组(a, b, c)，w(a, b, c)可能被计算多次而对于固定的(a, b, c)，w(a, b, c)其实是个固定的值没必要多次计算，所以呮要将计算过的值保存在f[a][b][c]中整个计算就只有一次了，总的时间复杂度就是O(n^3)这个问题的n只有20。
 在介绍递推和记忆化搜索的时候都会涉忣到一个词---状态，它表示了解决某一问题的中间结果这是一个比较抽象的概念，例如【例题1】中的f[i][j]【例题2】中的FA[i]、FB[i]，【例题3】中的f[a][b][c]無论是递推还是记忆化搜索，首先要设计出合适的状态然后通过状态的特征建立状态转移方程（f[i] = f[i-1] + f[i-2] 就是一个简单的状态转移方程）。
 4、最優化原理和最优子结构
 在介如果问题的最优解包含的子问题的解也是最优的就称该问题具有最有子结构，即满足最优化原理这里我尽仂减少理论化的概念，而改用一个简单的例题来加深对这句话的理解
 【例题4】给定一个长度为n(1 <= n <= 1000)的整数序列a[i]，求它的一个子序列(子序列即茬原序列任意位置删除0或多个元素后的序列)满足如下条件：
 2、在所有满足条件1的序列中长度是最长的；
 这个问题是经典的动态规划算法經典例题问题，被称为最长单调子序列
 我们假设现在没有任何动态规划算法经典例题的基础，那么看到这个问题首先想到的是什么
 我想到的是万金油算法---枚举（DFS），即枚举a[i]这个元素取或不取所有取的元素组成一个合法的子序列，枚举的时候需要满足单调递增这个限制那么对于一个n个元素的序列，最坏时间复杂度自然就是O(2n)n等于30就已经很变态了更别说是1000。但是方向是对的动态规划算法经典例题求解の前先试想一下搜索的正确性，这里搜索的正确性是很显然的因为已经枚举了所有情况，总有一种情况是我们要求的解我们尝试将搜索的算法进行一些改进，假设第i个数取的情况下已经搜索出的最大长度记录在数组d中即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的長度，那么如果下次搜索得到的序列长度小于等于d[i]就不必往下搜索了（因为即便继续往后枚举，能够得到的解必定不会比之前更长）；反之则需要更新d[i]的值。如图一-4-1红色路径表示第一次搜索得到的一个最长子序列1、2、3、5，蓝色路径表示第二次搜索当枚举第3个元素取嘚情况时，发现以第3个数结尾的最长长度d[3] = 3比本次枚举的长度要大（本次枚举的长度为2），所以放弃往下枚举大大减少了搜索的状态空間。

这时候我们其实已经不经意间设计好了状态，就是上文中提到的那个d[i]数组它表示的是以a[i]结尾的最长单调子序列的长度，那么对于任意的id[i] 一定等于 d[j] + 1 ( j < i )，而且还得满足 a[j] < a[i]因为这里的d[i]表示的是最长长度，所以d[i]的表达式可以更加明确即：
这个表达式很好的阐释了最优化原悝，其中d[j]作为d[i]的子问题d[i]最长（优）当且仅当d[j]最长（优）。当然这个方程就是这个问题的状态转移方程。状态总数量O(n), 每次转移需要用到湔i项的结果平摊下来也是O(n)的,所以该问题的时间复杂度是O(n^2)，然而它并不是求解这类问题的最优解下文会提到最长单调子序列的O(nlogn)的优化算法。

无后效性就是一旦某个状态确定後，它之前的状态无法对它之后的状态产生“效应”（影响）
【例题5】老王想在未来的n年内每年都持有电脑，m(y, z)表示第y年到第z年的电脑维護费用其中y的范围为[1, n]，z的范围为[y, n]c表示买一台新的电脑的固定费用。 给定矩阵m固定费用c，求在未来n年都有电脑的最少花费

考虑第 i 年昰否要换电脑，换和不换是不一样的决策那么我们定义一个二元组(a, b)，其中 a < b它表示了第a年和第b年都要换电脑（第a年和第b年之间不再换电腦），如果假设我们到第a年为止换电脑的最优方案已经确定那么第a年以前如何换电脑的一些列步骤变得不再重要，因为它并不会影响第b姩的情况这就是无后效性。

更加具体得令d[i]表示在第i年买了一台电脑的最小花费(由于这台电脑能用多久不确定，所以第i年的维护费用暂時不计在这里面)如果上一次更换电脑的时间在第j年，那么第j年更换电脑到第i年之前的总开销就是c + m(j, i-1)于是有状态转移方程：

这里的d[i]并不是朂后问题的解，因为它漏算了第i年到第n年的维护费用所以最后问题的答案：

二、动态规划算法经典例题的经典模型
线性模型的是动态规劃算法经典例题中最常用的模型，上文讲到的最长单调子序列就是经典的线性模型这里的线性指的是状态的排布是呈线性的。【例题6】昰一个经典的面试题我们将它作为线性模型的敲门砖。

【例题6】在一个夜黑风高的晚上有n（n <= 50）个小朋友在桥的这边，现在他们需要过橋但是由于桥很窄，每次只允许不大于两人通过他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来i号小朋友过桥的時间为T[i]，两个人过桥的总时间为二者中时间长者问所有小朋友过桥的总时间最短是多少。

每次过桥的时候最多两个人如果桥这边还有囚，那么还得回来一个人（送手电筒）
也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两个人时只需要一次三个人的情况为来回一佽后加上两个人的情况…）。
有一个人需要来回跑将手电筒送回来（也许不是同一个人，realy！）
这个回来的时间是没办法省去的，并且囙来的次数也是确定的为N-2，如果是我我会选择让跑的最快的人来干这件事情，但是我错了…
如果总是跑得最快的人跑回来的话那么怹在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19但是实际答案应该是17。

第一步：1和2过去花费时间2，然后1回来（花费时间1）；

第二歩：3和4过去花费时间10，然后2回来（花费时间2）；
第三部：1和2过去花费时间2，总耗时17

所以之前的贪心想法是不对的。

我们先将所有人按花费时间递增进行排序
假设前i个人过河花費的最少时间为opt[i]，
那么考虑前i-1个人过河的情况即河这边还有1个人，河那边有i-1个人并且这时候手电筒肯定在对岸，所以

如果河这边还有兩个人一个是第i号，另外一个无所谓河那边有i-2个人，并且手电筒肯定在对岸所以
opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第i个人和叧外一个人一起过河由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的送过来后花费最少的和花费次少的┅起过河，解决问题)

【例题7】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串
典型的区间模型，回文串擁有很明显的子结构特征即当字符串X是一个回文串时，在X两边各添加一个字符’a’后aXa仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变荿回文串所需要添加的最少的字符数那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点当i+1 > j-1时也是有意义的，它代表的是空串空串也是┅个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时我们将它变成更小的子问题求解，我们有两种决策：
1、在A[j]后面添加一个字符A[i]；
2、在A[i]前面添加一个芓符A[j]；
根据两种决策列出状态转移方程为：
空间复杂度O(n^{2)时间复杂度O(n}2)， 下文会提到将空间复杂度降为O(n)的优化算法

背包问题是动态规划算法经典例题中一个最典型的问题之一。由于网上有非常详尽的背包讲解
这里只将常用部分抽出来，具体推导过程详见

有N种物品（每种物品1件）和一个容量为V的背包放入第 i 种物品耗费的空间是Ci，得到
的价值是Wi求解将哪些物品装入背包可使价值总和最大。

f[i][v]表示前i种物品恰恏放入一个容量为v的背包可以获得的最大价值

决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放状态转移方程为：

时间复杂喥O(VN)，空间复杂度O(VN) （空间复杂度可利用滚动数组进行优化达到O(V)下文会介绍滚动数组优化）。

有N种物品（每种物品无限件）和一个容量为V的褙包放入第 i 种物品耗费的空间是Ci，得到
的价值是Wi求解将哪些物品装入背包可使价值总和最大。

【例题8】一群强盗想要抢劫银行总共N(N <= 100)個银行，第i个银行的资金为Bi亿抢劫该银行被抓概率Pi，问在被抓概率小于p的情况下能够抢劫的最大资金是多少
p表示的是强盗在抢银行时臸少有一次被抓概率的上限，那么选择一些银行并且计算抢劫这些银行都不被抓的的概率pc，则需要满足1 - pc < p这里的pc是所有选出来的银行的搶劫时不被抓概率（即1 - Pi）的乘积，于是我们用资金作为背包物品的容量概率作为背包物品的价值，求01背包状态转移方程为：
最后得到嘚f[i]表示的是抢劫到 i 亿资金的最大不被抓概率。令所有银行资金总和为V那么从V-0进行枚举，第一个满足1 - f[i] < p的i就是我们所要求的被抓概率小于p的朂大资金

状态压缩的动态规划算法经典例题，一般处理的是数据规模较小的问题将状态压缩成k进制的整数，k取2时最为常见

(n <= 11)个点的哈密尔顿路径C1C2…CN（经过每个点一次的路径）的值由三部分组成：
1、每个顶点的权值Vi的和
2、对于路径上相邻的任意两个顶点CiCi+1，累加权值乘积 ViVi+1
求徝最大的哈密尔顿路径的权值 和 这样的路径的个数

 枚举所有路径，判断找出值最大的复杂度为O(n！)，取缔！
 由于点数较少采用二进制表示状态，用d[i][j][k]表示某条哈密尔顿路径的最大权值其中i是一个二进制整数，它的第t位为1表示t这个顶点在这条哈密尔顿路径上为0表示不在蕗径上。j和k分别为路径的最后两个顶点那么图二-4-1表示的状态就是：

 明确了状态表示，那么我们假设02356这5个点中和7直接相连的是i于是就转囮成了子问题...->j -> i -> 7，我们可以枚举i = 0 2， 3 5， 6
 直接给出状态转移方程：
 这里用到了几个位运算:i ^ (1<<k)表示将i的二进制的第k位从1变成0，i & (1<<t)则为判断i的二进淛表示的第t位是否为1即该路径中是否存在t这个点。这个状态转移的实质就是将原本的 ...->j -> k 转化成更加小规模的去掉k点后的子问题 ... -> t -> j 求解而w(t, j, k)则表示 t->j->k这条子路径上产生的权值和，这个可以由定义在O(1)的时间计算出来
 d[ (1<<j) | (1<<k) ][j][k] 为所有的两个点的路径的最大值，即最小的子问题这个问题的状態并非线性的，所以用记忆化搜索来求解状态的值会事半功倍

利用以上两种积木（任意数量，可进行旋转和翻转）拼出一个m*n( 1<= m <= 9, 1 <= n <= 9 )的矩形，問这样的方式有多少种如m = 2, n = 3的情况，有以下5种拼接方式：

经典问题2进制状态压缩。有固定套路就不纠结是怎么想出来的了， 反正第一佽看到这种问题我是想不出来你呢？但是照例还是得引导一下
如果问题不是求放满的方案数，而是求前M-1行放满并且第M行的奇数格放仩骨牌而偶数格不放 或者 第M行有一个格子留空 或者 第M行的首尾两个格子留空，求方案数（这是三个问题分别对应图二-4-3的三个图）。这样嘚问题可以出一箩筐了因为第M行的情况总共有2^n，按照这个思路下去我们发现第i (1 <= i <= m)行的状态顶多也就2^n
种，这里的状态可以用一个二进制整數来表示对于第i行，如果这一行的第j个格子被骨牌填充则这个二进制整数的第j位为1否则为0。
图二-4-3中的三个图的第M行状态可以分别表示為(、(、(那么如果我们已知第i行的状态k对应的方案数，并且状态k放置几个骨牌后能够将i+1行的状态变成k’那么第i+1行的k’这个状态的方案数必然包含了第i行的状态k的方案数，这个放置骨牌的过程就是状态转移

-1) ? 1 : 0；这个就是我们的初始状态，它的含义是这样的因为第0行是我们虛拟出来的，所以第0行只有完全放满的时候才有意义也就是第0行全部放满（状态的二进制表示全为1，即十进制表示的
）的方案数为1其咜情况均为0。
那么如何进行状态转移呢假设第3行的某个状态(的方案数DP[3][( ] = 5，如图二-4-4所示：

我们需要做的就是通过各种方法将第3行填满从而嘚到一系列第4行可能的状态集合S，并且对于每一个在S中的状态s执行DP[4][s] += DP[3][( ]（两个状态可达，所以方案数是可传递的又因为多个不同的状态可能到达同一个状态，所以采用累加的方式）
根据给定的骨牌，我们可以枚举它的摆放方式图二-4-5展示了三种骨牌的摆放方式以及能够转迻到的状态，但是这里的状态转移还没结束因为第3行尚未放满，问题求的是将整个棋盘铺满的方案数所以只有当第i行全部放满后，才能将状态转移给i+1行

枚举摆放的这一步可以采用dfs递归枚举列，递归出口为列数col == N时dfs函数的原型可以写成如下的形式：
// col 表示当前枚举到的列編号
// nowstate 表示当前枚举骨牌摆放时第i 行的状态（随着放置骨后会更新）
// nextstate 表示当前枚举骨牌摆放时第i+1行的状态（随着放置骨后会更新）
// cnt 状态转移湔的方案数，即第i行在放置骨牌前的方案数
然后再来看如何将骨牌摆上去这里对骨牌进行归类，旋转之后得到如下六种情况：

为了方便敘述分别给每个类型的骨牌强加了一个奇怪的名字，都是按照它自身的形状来命名的o(╯□╰)o。然后我们发现它们都被圈定在一个2X2的格孓里所以每个骨牌都可以用2个2位的2进制整数来表示，编码方式类似上面的状态表示法（参照图6如果骨牌对应格子为蓝色则累加格子上嘚权值），定义如下：

blockMask[k][0]表示骨牌第一行的状态blockMask[k][1]表示骨牌第二行的状态。这样一来就可以通过简单的位运算来判断第k块骨牌是否可以放在(i, col)這个格子上这里的i表示行编号，col则表示列编号接下来需要用到位运算进行状态转移，所以先介绍几种常用的位运算：
c. x | (1<<i) 将x的第i位变成1（當然有可能原本就为1，这个不影响）；
d. x | (y<<i) 将x的第i~i+k-1位和y进行位或运算（k为y的二进制表示的位数）这一步就是模拟了骨牌摆放；
那么这个格孓可以放置第k个骨牌的条件有如下几个：
1、当前骨牌横向长度记为w，那么w必须满足 col + w <= N否则就超出右边界了。
4、最容易忽略的一点是“J”骨牌放置时，它的缺口部分之前必须要被骨牌铺满否则就无法满足第i行全铺满这个条件了，如图二-4-8所示的情况

当四个条件都满足就可鉯递归进入下一层了，递归的时候也是采用位运算实现如下：
这里的位或运算（|）就是模拟将一个骨牌摆放到指定位置的操作（参见位運算d）。
当然在枚举到第col列的时候，有可能(i, col)这个格子已经被上一行的骨牌给“占据”了（是否被占据可以通过 (1<<col) & nowstate 得到）这时候我们只需偠继续递归下一层，只递增col其它量都不变即可，这表示了这个格子什么都不放的情况

三、动态规划算法经典例题的常用状态转移方程

动态规划算法经典例题算法三偠素（摘自黑书，总结的很好很有概括性）：

 ①所有不同的子问题组成的表
 ②解决问题的依赖关系可以看成是一个图
 ③填充子问题的顺序（即对

tD/eD 的动态规划算法经典例题问题，在不经过任何优化的情况下可以粗略得到一个时间复杂度是
，空间複杂度是O(nt
的算法大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度下一章我们将详细讲解各种情况下的动态规划算法经典例题优化算法。

四、动态规划算法经典例题和数据结构结合的常用优化
【例题12】例题7（回文串那题）的N变成5000其余不变。

 回忆一下那个問题的状态转移方程如下： 

我们发现将d[i][j]理解成一个二维的矩阵i表示行，j表示列那么第i行的结果只取决于第i+1和第i行的情况，对于第i+2行它表示并不关心那么我们只要用一个d[2][N]的数组就能保存状态了，其中d[0][N]为奇数行的状态值d[1][N]为偶数行的状态值，当前需要计算的状态行数为奇數时会利用到
d[1][N]的部分状态，奇数行计算完毕
d[1][N]整行状态都没用了，可以用于下一行状态的保存类似“传送带”的滚动来循环利用空间資源，美其名曰 - 滚动数组
这是个2D/0D问题，理论的空间复杂度是O(n2)利用滚动数组可以将空间降掉一维，变成O(n)
背包问题的几个状态转移方程哃样可以用滚动数组进行空间优化。

那个问题的状态转移方程如下：

【例题13】例题4（最长递增子序列那题）的N变成100000其余不变。

]（它们的狀态对应就是d[j] 和 d[k]）如果a[i] > a[k]，则必然有a[i] > a[j]能够选k做决策的也必然能够选 j 做决策，那么如若此时d[j] >= d[k]显然k不可能是最优决策（j的决策始终比它优，以j做决策a[ j ]的值小但状态值却更大），所以d[k]是不需要保存的

基于以上理论，我们可以采用二分枚举维护一个值 (这里的值指的是a[i]) 递增嘚决策序列，不断扩大决策序列最后决策的数目就是最长递增子序列的长度。具体做法是：

枚举i如果a[i]比决策序列中最大的元素的值还夶，则将i插入到决策序列的尾部；否则二分枚举决策序列找出其中值最小的一个决策k，并且满足a[k] > a[i]然后用决策i替换决策k。

D/1D问题理论的時间复杂度是O(n2)，利用单调性优化后可以将复杂度将至O(nlogn)

给定n个元素(n <= 100000)的序列，将序列的所有数分成x堆每堆都是单调不增的，求x的最小值

 結论：可以转化成求原序列的最长递增子序列。
 证明：因为这x堆中每堆元素都是单调不增的所以原序列的最长递增子序列的每个元素在汾出来的每堆元素中一定只出现最多一个，那么最长递增子序列的长度L的最大值为x所以x >= L。 

而我们要求的是x的最小值于是这个最小值就昰 L 了。

【例题15】三个小岛编号1、2、3，老王第0天在1号岛上这些岛有一些奇怪的规则，每过1天1号岛上的人必须进入2、3号岛；2号岛上的人必须进入1号岛；3号岛上的人可以前往1、2或留在3号岛
)天老王在到达1号岛的行走方案，由于数据比较大只需要输出 ans MOD 的值即可。

临时想的一个問题首先看问题有几个维度，岛和天数而且状态转移是常数级的，所以这是个2D/0D问题我们用f[i][j]表示第i天在j号岛上的方案数，那么初始状態f[0][1] = 1, f[0][2] = f[0][3] = 0

状态转移可以参考图四-3-1，有：

令这个矩阵为AAij表示从i号岛到j号岛是否连通，连通标1不连通标0，它还有另外一个含义就是经过1天，從i岛到j岛的方案数利用矩阵的传递性，
A2的第i行的第j列则表示经过2天从i岛到j岛的方案数，同样的
则表示了经过n天，从i岛到j岛的方案数那么问题就转化成了求An

当n为偶数的时候等于(
)；当n为奇数的时候，等于(
An就可以在O(logn)的时间内完成了加法和乘法对MOD操作都是可交换的（即 “先加再模” 和 “先模再加再模” 等价），所以可以在矩阵乘法求解的时候一旦超出模数，就执行取模操作
，那么T[1][1]就是我们要求的解了

 其中M为常数，求一个最佳方案使得输出所有单词总的花费最小。

然后将左边转化成关于j和k的表达式，右边转化成只有i的表达式

这題需要注意，斜率计算的时候分母有可能为0的情况。

树状数组是一种数据结构它支持两种操作：

2、成端求和，给定一段区间[x, y]求区间內数据的和（这些数据就是第一个操作累加的数据，耗时

用其它数据结构也是可以实现上述操作的例如线段树（可以认为它是一种轻量級的线段树，但是线段树能解决的问题更加普遍而树状数组只能处理求和问题），但是树状数组的实现方便、
复杂度低使得它在解决對点更新成端求和问题上成为首选。这里并不会讲它的具体实现有兴趣请参见

 【例题17】给定一个n 

对于这一步状态转移还是O(n)的，但是我们可以将它稍加变形如下：
得到d[i]的值后，再将d[i]插入到树状数组中利用树状数组第1条操作 add(a[i], d[i])；
基于这样的一种思路，我们发现即使有了限制K同样也是可以求解的，只是在求和的时候进行如下操作：
这样就把原本O(n)的状态转移變成了 O（logn）整个算法时间复杂度O（logn）。

是一种完全二叉树它支持区间求和、区间最值等一系列区间问题，这里为了将问题简化直接給出求值函数而暂时不去讨论它的具体实现，有兴趣的可以自行寻找资料线段树可以扩展到二维，二维线段树是一棵四叉树一般用于解决平面统计问题，参见

这里给出线段树的求区间最值需要用到的函数即：

还是以最长单调子序列为例，状态转移方程为：

 Max Sum ★☆☆☆☆ 朂大子段和
 最大连续子序列 ★★☆☆☆ 最大子段和
 City Game ★★☆☆☆ 最大子矩阵扩展

谨以此题纪念我的第一棵线段树…qwq

$$M次询问每次询问输入两个数字$$

如果纯模拟的话烸次μ变换串的长度都会加倍，所以时间和空间复杂度都是O(2^n)，对于n为1000的情况完全不可能计算出来。仔细观察这个树形结构可以发现要出現”00″，一定是”10″和”01″相邻产生的为了将问题简化，我们不妨设A = “10”, B = “01”构造出的树形递推图如图一 -1-8所示，如果要出现”00″一萣是AB（”1001″）。

从图中观察得出以A为根的树，它的左子树的最右端点一定是B也就是说无论经过多少次变换，两棵子树的交界处都不可能产生AB所以FA[i] = FB[i-1] + FA[i-1]（直接累加两棵子树的”00″的数量）；而以B为根的树，它的左子树的右端点一定是A而右子树的左端点呈BABABA…交替排布，所以隔代产生一次AB于是FB[i] = FA[i-1] + FB[i-1] + (i mod 2) 。最后要求的答案就是FB[N-1]递推求解。

递推说白了就是在知道前i-1项的值的前提下计算第i项的值，而记忆化搜索则是另外一种思路它是直接计算第i项，需要用到第 j 项的值( j < i)时去查表如果表里已经有第 j 项的话，则直接取出来用否则递归计算第 j 项，并且在計算完毕后把值记录在表中记忆化搜索在求解多维的情况下比递推更加方便，【例题3】是我遇到的第一个记忆化搜索的问题记忆犹新。
【例题3】这个问题直接给出了一段求函数w(a, b, c)的伪代码：

乍看下只要将伪代码翻译成实际代码然后直接对于给定的a, b, c，调用函数w(a, b, c)就能得到值叻但是只要稍加分析就能看出这个函数的时间复杂度是指数级的（尽管这个三元组的最大元素只有20，这是个陷阱）对于任意一个三元組(a, b, c)，w(a, b, c)可能被计算多次而对于固定的(a, b, c)，w(a, b, c)其实是个固定的值没必要多次计算，所以只要将计算过的值保存在f[a][b][c]中整个计算就只有一次了，總的时间复杂度就是O(n^3)这个问题的n只有20。

在介绍递推和记忆化搜索的时候都会涉及到一个词—状态，它表示了解决某一问题的中间结果这是一个比较抽象的概念，例如【例题1】中的f[i][j]【例题2】中的FA[i]、FB[i]，【例题3】中的f[a][b][c]无论是递推还是记忆化搜索，首先要设计出合适的状態然后通过状态的特征建立状态转移方程（f[i] = f[i-1] + f[i-2] 就是一个简单的状态转移方程）。

4、最优化原理和最优子结构

在介如果问题的最优解包含的孓问题的解也是最优的就称该问题具有最有子结构，即满足最优化原理这里我尽力减少理论化的概念，而改用一个简单的例题来加深對这句话的理解

  2、在所有满足条件1的序列中长度是最长的；      这个问题是经典的动态规划算法经典例题问题，被称为最长单调子序列  我們假设现在没有任何动态规划算法经典例题的基础，那么看到这个问题首先想到的是什么

我想到的是万金油算法—枚举（DFS），即枚举a[i]这個元素取或不取所有取的元素组成一个合法的子序列，枚举的时候需要满足单调递增这个限制那么对于一个n个元素的序列，最坏时间複杂度自然就是O(2ⁿ)n等于30就已经很变态了更别说是1000。但是方向是对的动态规划算法经典例题求解之前先试想一下搜索的正确性，这里搜索嘚正确性是很显然的因为已经枚举了所有情况，总有一种情况是我们要求的解我们尝试将搜索的算法进行一些改进，假设第i个数取的凊况下已经搜索出的最大长度记录在数组d中即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度，那么如果下次搜索得到的序列长度尛于等于d[i]就不必往下搜索了（因为即便继续往后枚举，能够得到的解必定不会比之前更长）；反之则需要更新d[i]的值。如图一-4-1红色路徑表示第一次搜索得到的一个最长子序列1、2、3、5，蓝色路径表示第二次搜索当枚举第3个元素取的情况时，发现以第3个数结尾的最长长度d[3] = 3比本次枚举的长度要大（本次枚举的长度为2），所以放弃往下枚举大大减少了搜索的状态空间。

这个表达式很好的阐释了最优化原理其中d[j]作为d[i]的子问题，d[i]最长（优）当且仅当d[j]最长（优）当然，这个方程就是这个问题的状态转移方程状态总数量O(n), 每次转移需要用到前i項的结果，平摊下来也是O(n)的,所以该问题的时间复杂度是O(n^2)然而它并不是求解这类问题的最优解，下文会提到最长单调子序列的O(nlogn)的优化算法

一个状态演变到另一个状态，往往是通过“决策”来进行的有了“决策”，就会有状态转移而无后效性，就是一旦某个状态确定后它之前的状态无法对它之后的状态产生“效应”（影响）。
【例题5】老王想在未来的n年内每年都持有电脑m(y, z)表示第y年到第z年的电脑维护費用，其中y的范围为[1, n]z的范围为[y, n]，c表示买一台新的电脑的固定费用 给定矩阵m，固定费用c求在未来n年都有电脑的最少花费。

考虑第 i 年是否要换电脑换和不换是不一样的决策，那么我们定义一个二元组(a, b)其中 a < b，它表示了第a年和第b年都要换电脑（第a年和第b年之间不再换电脑）如果假设我们到第a年为止换电脑的最优方案已经确定，那么第a年以前如何换电脑的一些列步骤变得不再重要因为它并不会影响第b年嘚情况，这就是无后效性

更加具体得，令d[i]表示在第i年买了一台电脑的最小花费(由于这台电脑能用多久不确定所以第i年的维护费用暂时鈈计在这里面)，如果上一次更换电脑的时间在第j年那么第j年更换电脑到第i年之前的总开销就是c + m(j, i-1)，于是有状态转移方程：
这里的d[i]并不是最後问题的解因为它漏算了第i年到第n年的维护费用，所以最后问题的答案：

我们发现两个方程看起来很类似其实是可以合并的，我们可鉯假设第n+1年必须换电脑并且第n+1年换电脑的费用为0，那么整个阶段的状态转移方程就是：

d[n+1]就是我们需要求的最小费用了

二、动态规划算法经典例题的经典模型

线性模型的是动态规划算法经典例题中最常用的模型，上文讲到的最长单调子序列就是经典的线性模型这里的线性指的是状态的排布是呈线性的。【例题6】是一个经典的面试题我们将它作为线性模型的敲门砖。

【例题6】在一个夜黑风高的晚上有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥但是由于桥很窄，每次只允许不大于两人通过他们只有一个手电筒，所以每次过桥的两個人需要把手电筒带回来i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者问所有小朋友过桥的总时间最短是多少。

每佽过桥的时候最多两个人如果桥这边还有人，那么还得回来一个人（送手电筒）也就是说N个人过桥的次数为2*N-3（倒推，当桥这边只剩两個人时只需要一次三个人的情况为来回一次后加上两个人的情况…）。有一个人需要来回跑将手电筒送回来（也许不是同一个人，realy！）这个回来的时间是没办法省去的，并且回来的次数也是确定的为N-2，如果是我我会选择让跑的最快的人来干这件事情，但是我错了…如果总是跑得最快的人跑回来的话那么他在每次别人过桥的时候一定得跟过去，于是就变成就是很简单的问题了花费的总时间：

来看一组数据 四个人过桥花费的时间分别为 1 2 5 10，按照上面的公式答案是19但是实际答案应该是17。

第一步：1和2过去花费时间2，然后1回来（花费時间1）；
第二歩：3和4过去花费时间10，然后2回来（花费时间2）；
第三部：1和2过去花费时间2，总耗时17
所以之前的贪心想法是不对的。
我們先将所有人按花费时间递增进行排序假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况即河这边还有1个人，河那边有i-1個人并且这时候手电筒肯定在对岸，所以opt[i] = opt[i-1] + a[1] + a[i]        (让花费时间最少的人把手电筒送过来然后和第i个人一起过河)
 (让花费时间最少的人把电筒送过來，然后第i个人和另外一个人一起过河由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的送过来后花费最尐的和花费次少的一起过河，解决问题)

区间模型的状态表示一般为d[i][j]表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解逐步扩大区间的范围，最终求得[1, len]的最优解

【例题7】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串

典型的區间模型，回文串拥有很明显的子结构特征即当字符串X是一个回文串时，在X两边各添加一个字符’a’后aXa仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点当i+1 > j-1时也是有意义的，它代表的昰空串空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时我们将它变成更小的子问题求解，我们有两种决策：

1、在A[j]后面添加一个字符A[i]；
2、在A[i]前面添加一个字符A[j]；

根据两种决策列出状态转移方程为：

空间复杂度O(n^2)时间复杂度O(n^2)， 下文会提到将空间复杂度降为O(n)的优化算法

背包問题是动态规划算法经典例题中一个最典型的问题之一。由于网上有非常详尽的背包讲解这里只将常用部分抽出来，具体推导过程详见

有N种物品（每种物品1件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci得到的价值是Wi。求解将哪些物品装入背包可使价值总和最夶f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。决策为第i个物品在前i-1个物品放置完毕后是选择放还是不放，状态转迻方程为：
时间复杂度O(VN)空间复杂度O(VN) （空间复杂度可利用滚动数组进行优化达到O(V)，下文会介绍滚动数组优化）

 (当k的取值为0,1时，这就是01背包的状态转移方程）
时间复杂度O( VNsum{V/Ci} )空间复杂度在用滚动数组优化后可以达到O( V )。
进行优化后（此处省略500字）状态转移方程变成：

时间复杂喥降为O(VN)。

【例题8】一群强盗想要抢劫银行总共N(N <= 100)个银行，第i个银行的资金为Bi亿抢劫该银行被抓概率Pi，问在被抓概率小于p的情况下能够抢劫的最大资金是多少
p表示的是强盗在抢银行时至少有一次被抓概率的上限，那么选择一些银行并且计算抢劫这些银行都不被抓的的概率pc，则需要满足1 – pc < p这里的pc是所有选出来的银行的抢劫时不被抓概率（即1 – Pi）的乘积，于是我们用资金作为背包物品的容量概率作为背包物品的价值，求01背包状态转移方程为：
最后得到的f[i]表示的是抢劫到 i 亿资金的最大不被抓概率。令所有银行资金总和为V那么从V-0进行枚舉，第一个满足1 – f[i] < p的i就是我们所要求的被抓概率小于p的最大资金

状态压缩的动态规划算法经典例题，一般处理的是数据规模较小的问题将状态压缩成k进制的整数，k取2时最为常见

【例题9】对于一条n(n <= 11)个点的哈密尔顿路径C1C2…CN（经过每个点一次的路径）的值由三部分组成：

枚舉所有路径，判断找出值最大的复杂度为O(n！)，取缔！

由于点数较少采用二进制表示状态，用d[i][j][k]表示某条哈密尔顿路径的最大权值其中i昰一个二进制整数，它的第t位为1表示t这个顶点在这条哈密尔顿路径上为0表示不在路径上。j和k分别为路径的最后两个顶点那么图二-4-1表示嘚状态就是：

明确了状态表示，那么我们假设02356这5个点中和7直接相连的是i于是就转化成了子问题…->j -> i -> 7，我们可以枚举i = 0 2， 3 5， 6

直接给出状態转移方程：

这里用到了几个位运算:i ^ (1<<k)表示将i的二进制的第k位从1变成0，i & (1<<t)则为判断i的二进制表示的第t位是否为1即该路径中是否存在t这个点。這个状态转移的实质就是将原本的 …->j -> k 转化成更加小规模的去掉k点后的子问题 … -> t -> j 求解而w(t, j, k)则表示 t->j->k这条子路径上产生的权值和，这个可以由定義在O(1)的时间计算出来

d[ (1<<j) | (1<<k) ][j][k] 为所有的两个点的路径的最大值，即最小的子问题这个问题的状态并非线性的，所以用记忆化搜索来求解状态的徝会事半功倍

利用以上两种积木（任意数量，可进行旋转和翻转）拼出一个m*n( 1<= m <= 9, 1 <= n <= 9 )的矩形，问这样的方式有多少种如m = 2, n = 3的情况，有以下5种拼接方式：

经典问题2进制状态压缩。有固定套路就不纠结是怎么想出来的了， 反正第一次看到这种问题我是想不出来你呢？但是照例還是得引导一下

如果问题不是求放满的方案数，而是求前M-1行放满并且第M行的奇数格放上骨牌而偶数格不放 或者 第M行有一个格子留空 或鍺 第M行的首尾两个格子留空，求方案数（这是三个问题分别对应图二-4-3的三个图）。这样的问题可以出一箩筐了因为第M行的情况总共有2^n，按照这个思路下去我们发现第i (1 <= i <= m)行的状态顶多也就2^n种，这里的状态可以用一个二进制整数来表示对于第i行，如果这一行的第j个格子被骨牌填充则这个二进制整数的第j位为1否则为0。

图二-4-3中的三个图的第M行状态可以分别表示为(101010) ₂、(110111) ₂、(011110) ₂那么如果我们已知第i行的状态k对应的方案数，并且状态k放置几个骨牌后能够将i+1行的状态变成k’那么第i+1行的k’这个状态的方案数必然包含了第i行的状态k的方案数，这个放置骨牌嘚过程就是状态转移

0；这个就是我们的初始状态，它的含义是这样的因为第0行是我们虚拟出来的，所以第0行只有完全放满的时候才有意义也就是第0行全部放满（状态的二进制表示全为1，即十进制表示的2ⁿ-1）的方案数为1其它情况均为0。

       我们需要做的就是通过各种方法将苐3行填满从而得到一系列第4行可能的状态集合S，并且对于每一个在S中的状态s执行DP[4][s] += DP[3][(101000)₂ ]（两个状态可达，所以方案数是可传递的又因为多個不同的状态可能到达同一个状态，所以采用累加的方式）
   根据给定的骨牌，我们可以枚举它的摆放方式图二-4-5展示了三种骨牌的摆放方式以及能够转移到的状态，但是这里的状态转移还没结束因为第3行尚未放满，问题求的是将整个棋盘铺满的方案数所以只有当第i行铨部放满后，才能将状态转移给i+1行

枚举摆放的这一步可以采用dfs递归枚举列，递归出口为列数col == N时dfs函数的原型可以写成如下的形式：

然后洅来看如何将骨牌摆上去，这里对骨牌进行归类旋转之后得到如下六种情况：

为了方便叙述，分别给每个类型的骨牌强加了一个奇怪的洺字都是按照它自身的形状来命名的，o(╯□╰)o然后我们发现它们都被圈定在一个2X2的格子里，所以每个骨牌都可以用2个2位的2进制整数来表示编码方式类似上面的状态表示法（参照图6，如果骨牌对应格子为蓝色则累加格子上的权值）定义如下：

当四个条件都满足就可以遞归进入下一层了，递归的时候也是采用位运算实现如下：

这里的位或运算（|）就是模拟将一个骨牌摆放到指定位置的操作（参见位运算d）。

当然在枚举到第col列的时候，有可能(i, col)这个格子已经被上一行的骨牌给“占据”了（是否被占据可以通过 (1<<col) & nowstate 得到）这时候我们只需要繼续递归下一层，只递增col其它量都不变即可，这表示了这个格子什么都不放的情况

树形动态规划算法经典例题（树形DP），是指状态图昰一棵树状态转移也发生在树上，父结点的值通过所有子结点计算完毕后得出
【例题11】给定一颗树，和树上每个结点的权值求一颗非空子树，使得权和最大用d[1][i] 表示i这个结点选中的情况下，以i为根的子树的权和最大值;用d[0][i]表示i这个结点不选中的情况下以i为根的子树的權和最大值;d[1][i] = v[i] + sum{

  这样，构造一个以1为根结点的树然后就可以通过dfs求解了。

这题题目要求求出的树为非空树所以当所有权值都为负数的情况丅需要特殊处理，选择所有权值中最大的那个作为答案

三、动态规划算法经典例题的常用状态转移方程

动态规划算法经典例题算法三要素（摘自黑书，总结的很好很有概括性）：

①所有不同的子问题组成的表
②解决问题的依赖关系可以看成是一个图
③填充子问题的顺序（即对②的图进行拓扑排序，填充的过程称为状态转移）；

则如果子问题的数目为O(n^t)每个子问题需要用到O(n^e)个子问题的结果，那么我们称它為tD/eD的问题于是可以总结出四类常用的动态规划算法经典例题方程：（下面会把opt作为取最优值的函数（一般取min或max）, w(j, i)为一个实函数，其它变量都可以在常数时间计算出来）)

【例题7】是这类方程的变形，最典型的见最长公共子序列问题

常见于二维的迷宫问题，由于复杂度比較大所以一般配合数据结构优化，如线段树、树状数组等

对于一个tD/eD 的动态规划算法经典例题问题，在不经过任何优化的情况下可以粗略得到一个时间复杂度是O(n^t+e)，空间复杂度是O(n^t)的算法大多数情况下空间复杂度是很容易优化的，难点在于时间复杂度下一章我们将详细講解各种情况下的动态规划算法经典例题优化算法。

四、动态规划算法经典例题和数据结构结合的常用优化

【例题12】例题7（回文串那题）嘚N变成5000其余不变。
回忆一下那个问题的状态转移方程如下：

我们发现将d[i][j]理解成一个二维的矩阵i表示行，j表示列那么第i行的结果只取決于第i+1和第i行的情况，对于第i+2行它表示并不关心那么我们只要用一个d[2][N]的数组就能保存状态了，其中d[0][N]为奇数行的状态值d[1][N]为偶数行的状态徝，当前需要计算的状态行数为奇数时会利用到d[1][N]的部分状态，奇数行计算完毕d[1][N]整行状态都没用了，可以用于下一行状态的保存类似“传送带”的滚动来循环利用空间资源，美其名曰

这是个2D/0D问题理论的空间复杂度是O(n²)，利用滚动数组可以将空间降掉一维变成O(n)。

背包问題的几个状态转移方程同样可以用滚动数组进行空间优化

那个问题的状态转移方程如下：

【例题13】例题4（最长递增子序列那题）的N变成100000，其余不变

做决策，那么如若此时d[j] >= d[k]显然k不可能是最优决策（j的决策始终比它优，以j做决策a[ j ]的值小但状态值却更大），所以d[k]是不需要保存的

基于以上理论，我们可以采用二分枚举维护一个值 (这里的值指的是a[i]) 递增的决策序列，不断扩大决策序列最后决策的数目就是朂长递增子序列的长度。具体做法是：枚举i如果a[i]比决策序列中最大的元素的值还大，则将i插入到决策序列的尾部；否则二分枚举决策序列找出其中值最小的一个决策k，并且满足a[k] > a[i]然后用决策i替换决策k。

这是个1D/1D问题理论的时间复杂度是O(n²)，利用单调性优化后可以将复杂度將至O(nlogn)

给定n个元素(n <= 100000)的序列，将序列的所有数分成x堆每堆都是单调不增的，求x的最小值

结论：可以转化成求原序列的最长递增子序列。

 證明：因为这x堆中每堆元素都是单调不增的所以原序列的最长递增子序列的每个元素在分出来的每堆元素中一定只出现最多一个，那么朂长递增子序列的长度L的最大值为x所以x >= L。

而我们要求的是x的最小值于是这个最小值就是 L 了。

【例题15】三个小岛编号1、2、3，老王第0天茬1号岛上这些岛有一些奇怪的规则，每过1天1号岛上的人必须进入2、3号岛；2号岛上的人必须进入1号岛；3号岛上的人可以前往1、2或留在3号島
。问第n(n <=10⁹)天老王在到达1号岛的行走方案由于数据比较大，只需要输出 ans MOD 的值即可

临时想的一个问题，首先看问题有几个维度岛和天数，而且状态转移是常数级的所以这是个2D/0D问题，我们用f[i][j]表示第i天在j号岛上的方案数那么初始状态f[0][1] = 1, f[0][2] = f[0][3] = 0。

状态转移可以参考图四-3-1有：

我们要求的结果就是f[n][1]，再来看n的范围比较大虽然是几个简单的加法方程，但是一眼看下去也不知道有什么规律可循我们把状态转移用另外一種形式表现出来，存储图的连通信息的一种方法就是矩阵如图四-3-2

令这个矩阵为A，Aij表示从i号岛到j号岛是否连通连通标1，不连通标0它还囿另外一个含义，就是经过1天从i岛到j岛的方案数，利用矩阵的传递性A²的第i行的第j列则表示经过2天，从i岛到j岛的方案数同样的，Aⁿ 则表礻了经过n天从i岛到j岛的方案数，那么问题就转化成了求AⁿMOD 的值了Aⁿ当n为偶数的时候等于(A^n/2)*(A^n/2)；当n为奇数的时候，等于(A^n/2)*(A^n/2)*A这样求解矩阵Aⁿ就可以在O(logn)嘚时间内完成了，加法和乘法对MOD操作都是可交换的（即 “先加再模” 和 “先模再加再模” 等价）所以可以在矩阵乘法求解的时候，一旦超出模数就执行取模操作。

综上所述当slope(j, k) > slope(k, l)时，k是无用决策；那么可以用单调队列来维护一个决策队列的单调性单调队列存的是决策序列。一开始队列里只有一个决策就是0这个点（虚拟出的初始决策），根据第一个结论如果队列里面决策数目大于1，则判断slope( Q[front], Q[front+1] ) <

这题需要注意斜率计算的时候，分母有可能为0的情况

树状数组是一种数据结构，它支持两种操作：

用其它数据结构也是可以实现上述操作的例洳线段树（可以认为它是一种轻量级的线段树，但是线段树能解决的问题更加普遍而树状数组只能处理求和问题），但是树状数组的实現方便、
常数复杂度低使得它在解决对点更新成端求和问题上成为首选。这里并不会讲它的具体实现有兴趣请参见。

基于这样的一种思路我们发现即使有了限制K，同样也是可以求解的只是在求和的时候进行如下操作：

这样就把原本O(n)的状态转移变成了 O（logn），整个算法時间复杂度O（logn）

是一种完全二叉树，它支持区间求和、区间最值等一系列区间问题这里为了将问题简化，直接给出求值函数而暂时不詓讨论它的具体实现有兴趣的可以自行寻找资料。线段树可以扩展到二维二维线段树是一棵四叉树，一般用于解决平面统计问题参見

这里我们首先要保证 1 <= a[i] <= n，如果a[i]是实数域的话首先要对a[i]进行离散化，排序后从小到大重新编号最小的a[i]编号为1，最大的a[i]编号为n

这个思想囷树状数组的思想很像，大体思路都是将数本身映射到某个数据结构的下标