【精品计划1】动态规划入门到熟悉，看不懂来打我啊

太过爱你忘了你带给我的痛 2024-04-18 12:49 137阅读 0赞

持续更新。。。。。。

## 2.1斐波那契系列问题 ##

## 2.2矩阵系列问题 ##

## 2.3跳跃系列问题 ##

## 3.1 01背包 ##

## 3.2 完全背包 ##

## 3.3多重背包 ##

## 3.4 一些变形选讲 ##

## 2.1斐波那契系列问题 ##

在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N\*）根据定义，前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55

例1：给定一个正整数n，求出斐波那契数列第n项（这时n较小）

解法一：完全抄定义

def f(n):
    	if n==1 or n==2:
       		return 1
    	return f(n-1)+f(n-2)

分析一下，为什么说递归效率很低呢？咱们来试着运行一下就知道了：

比如想求f(10)，计算机里怎么运行的？

![https://img-blog.csdn.net/20180412131244538][https_img-blog.csdn.net_20180412131244538]

想算出f(10)，就要先算出F(9),

想算出f(9)，就要先算出F(8),

想算出f(8)，就要先算出F(7),

想算出f(7)，就要先算出F(6)……

兜了一圈，我们发现，有相当多的计算都重复了，比如红框部分：

![20190906185552723.png][]

那如何解决这个问题呢？问题的原因就在于，我们算出来某个结果，并没有记录下来，导致了重复计算。那很容易想到如果我们把计算的结果全都保存下来，按照一定的顺序推出n项，就可以提升效率

解法2：

def f1(n):
        if n==1 or n==2:
            return 1
        l=[0]*n                #保存结果
        l[0],l[1]=1,1            #赋初值
        for i in range(2,n):
            l[i]=l[i-1]+l[i-2]     #直接利用之前结果
        return l[-1]

可以看出，时间o(n)，空间o(n)。

继续思考，既然只求第n项，而斐波那契又严格依赖前两项，那我们何必记录那么多值浪费空间呢？只记录前两项就可以了。

解法3：

def f2(n):
        a,b=1,1
        for i in range(n-1):
            a,b=b,a+b
        return a

补充：

1.  pat、蓝桥杯等比赛原题：求的n很大，F(N)模一个数。应每个结果都对这个数取模，否则：第一，计算量巨大，浪费时间；第二，数据太大，爆内存，
2.  对于有多组输入并且所求结果类似的题，可以先求出所有结果存起来，然后直接接受每一个元素，在表中查找相应答案
3.  此题有快速幂算法，但是碍于篇幅和同学们水平有限，不再叙述，可以自行学习。

例2：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

依旧是找递推关系：

1）跳一阶，就一种方法

2）跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种

3）三个及三个以上，假设为n阶，青蛙可以是跳一阶来到这里，或者跳两阶来到这里，只有这两种方法。

它跳一阶来到这里，说明它上一次跳到n-1阶，

同理，它也可以从n-2跳过来

![20190906185640844.png][]

f（n）为跳到n的方法数，所以，f(n)=f(n-1)+f(n-2)

优化思路与例1类似，请自行思考。

例3：我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2\*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

N=1: 只有一种

N=2，两种:

![20190906185655908.png][]

N=3:

![2019090618570111.png][]

读到这里，你们应该能很快想到，依旧是斐波那契式递归啊。

对于n>=3:怎么能覆盖到三？

只有两种办法，从n-1的地方竖着放了一块，或者从n-2的位置横着放了两块

例4：给定一个由0-9组成的字符串，1可以转化成A，2可以转化成B。依此类推。。25可以转化成Y，26可以转化成z，给一个字符串，返回能转化的字母串的有几种？

比如：123，可以转化成

1 、2 、3变成ABC，

12 、3变成LC，

1 、23变成AW

三种，返回三，

比如99999，就一种：iiiii，返回一。

分析：求i位置及之前字符能转化多少种。

两种转化方法

1）字符i自己转换成自己对应的字母

2）和前面那个数组成两位数，然后转换成对应的字母

假设遍历到i位置，判断i-1位置和i位置组成的两位数是否大于26，大于就没有第二种方法，f(i)=f(i-1),如果小于26， f(i)=f(i-1)+f(i-2)

## 2.2矩阵系列问题 ##

例5：给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最小路径和。

1 3 5 9

8 1 3 4

5 0 6 1

8 8 4 0

路径：1 3 1 0 6 1 0路径和最小，返回12

分析：我们可以像之前一样，暴力的把每一种情况都试一次，但是依旧会造成过多的重复计算，以本题为例子最后解释一下暴力慢在哪里，以后不再叙述了。

比如本题来讲，我们尝试如下路径：

![20190906185823196.png][]![2019090618582942.png][]

有很多路是重复走过的一遍。

再进一步说：

![20190906185835607.png][]

从1到6位置，有很多路可以走，直观感受一下：

![20190906185903993.png][]

所有路中，一定会有和最小的，但是我们并不知道，每次尝试一次1->6->终点的路线时，我们把所有的情况都算了一遍，这过程中我们浪费了相当多的有效信息。

这就是暴力的结果。

优化做法：生成和矩阵相同大小的二维表，用来记录到起点每个位置的最小路径和

![20190906185915775.png][]

接下来带着大家真正进入动态规划；

第一步：初始化（对于本题来说，第一列和第一行，我们别无选择，就一条路，因此，我们可以直接确定答案）

![20190906185926488.png][]

第二步：确定其余位置如何推出（我们称为状态转移方程）

直观来说，每个位置只可能是从上面，或者左边走来的：

![20190906190015908.png][]

对于普遍的位置i，j，只有i-1,j和i,j-1这两个位置可以一步走到这里，所以

DP\[i,j\]=min(DP\[i,j-1\],DP\[i-1,j\]）+L\[i,j\]（之前的最优解加上本位置的数字）

继续优化：和之前一样，这个式子实际上也是严格依赖两个值，一个是左边的值，一个是上面的值，所以，我们按之前的思路，应该可以想到可以压缩空间。

我们尝试用一维的空间来解题：

想象这是我们的第一行答案：

![20190906190027990.png][]

我们如何利用仅有的一维空间来更新出下一行呢？

我们要想：

*  我们需要左面的数字，所以，本位置的左边必须是更新过的数字（否则就是左上的位置了），所以应该从左往右更新。
 *  我们需要上面的数字，这个不需要更新，本来就需要本位置的旧数字。

本题第二行为：8，1，3，4

第一行答案为

![20190906190044145.png][]

依次更新：

更新A：

![20190906190058210.png][]

（只能向下走）

更新B：

![20190906190115903.png][]

（比较从左边来和从上面来哪里比较小）

更新C：

![20190906190126337.png][]

更新D：

![20190906190135593.png][]

最后我们可以发现，伪代码是这样的：

For i 0 -> 高度:

For j 0 -> 宽度

DP\[j\]=min(DP\[j-1\],DP\[j\]）+L\[i,j\]

时间不变，空间优化到o(min（高，宽））

例6：给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最大路径和。

和例5只差一个“大”字，请自己思考

例7：一个矩阵，初始在左上角，要求每次只能向下或向右移动，求到终点的方法数。

和例5，6类似，只是方法数应该等于，左边的方法数加上上面的方法数

第二章末练习

一个只包含'A'、'B'和'C'的字符串，如果存在某一段长度为3的连续子串中恰好'A'、'B'和'C'各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：

BAACAACCBAAA 连续子串"CBA"中包含了'A','B','C'各一个，所以是纯净的字符串

AABBCCAABB 不存在一个长度为3的连续子串包含'A','B','C',所以是暗黑的字符串

你的任务就是计算出长度为n的字符串(只包含'A'、'B'和'C')，有多少个是暗黑的字符串。(网易17校招原题)

2、X国的一段古城墙的顶端可以看成 2\*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。

![https://img-blog.csdn.net/20180506110603122][https_img-blog.csdn.net_20180506110603122]

你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）

比如：a d b c e f 就是合格的刷漆顺序。

c e f d a b 是另一种合适的方案。

当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。

## 3.1 01背包 ##

入门了动态规划之后，我们来看一个经典系列问题：背包问题

![2019090619015848.png][]

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：

f\[i\]\[j\]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程为：

![20190906190210796.png][]

“将前i件物品放入容量为j的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i−1件物品的问题。

如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为j的背包中”，价值为f\[i−1\]\[j\]；

如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为j−c\[i\]的背包中”，此时能获得的最大价值就是f\[i−1\]\[j−w\[i\]\],再加上通过放入第i件物品获得的价值v\[i\]。

因此得出上面的式子。

继续优化空间（利用之前提到的知识）：

如果我们压缩到一维空间解题，这次我们需要的是上面的位置和左上的位置，也就是说，我们需要左边的位置是没被更新过的，得出更新顺序应该从右往左：

for i in range(1,n+1):

for j in range(v,-1,-1)

f\[j\] = max(f\[j\], f\[j - w\[i\]\] + v\[i\]);

## 3.2 完全背包 ##

![2019090619030419.png][]

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,很容易得出：

![20190906190224227.png][]

这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了

而是![2019090619031338.png][]，总的复杂度可以认为是![2019090619031868.png][],将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

我们可以知道，对于一个普遍位置w，当前物品代价为2的话，下图中红色区域就是和位置w的取值相关的一些数值：

![20190906190332507.png][]

对当前物品的决策就依次是：不拿、拿一个、拿两个、拿三个（对应上面式子中的k）

我们算法优化的思路就是不断去除重复计算，显然我们可以继续优化这个式子。

请思考：我们的E3位置是如何得出的？其实是根据三个红色区域得出的，但是我们算位置w时又算了一遍，显然是重复了。而E3其实包含了不拿、拿一个、拿两个这些情况中的最优解，我们算w时直接用就可以了。

给出模板代码：

for (int i = 1; i <= n; i++)

for (int j = w\[i\]; j <= V; j++)

f\[j\] = max(f\[j\], f\[j - w\[i\]\] + v\[i\]);

对比两种背包：

这个代码与01背包的代码只有j的循环次序不同而已。为什么这样一改就可行呢？

首先想想为什么01背包中要按照j=V...0 j=V...0j=V...0的逆序来循环。这是因为要保证第i次循环中的状态f\[i\]\[j\]是由状态f\[i−1\]\[j−w\[i\]\]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f\[i−1\]\[j−w\[i\]\]。

而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i ii种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f\[i\]\[j−w\[i\]\]，所以就可以并且必须采用j=0...V j=0...Vj=0...V的顺序循环。这就是这个简单的程序为何成立的道理。

最终给出状态转移方程给不明白的同学看：

![20190906190346828.png][]

（也可以通过数学导出此式）

## 3.3多重背包 ##

![20190906190420422.png][]

和之前的背包不同，每种物品不是只有一件，也不是有无限件，这次的每种物品的数量都是有限制的，我们对于每种物品，可以选择拿一件、两件……p\[i\]件。

我们借用上一种问题的图：

![20190906190410550.png][]

看起来是类似的，位置w依旧和红色区域相关，但是我们可以直接根据E3来求出位置w吗？是不能的，因为条件变了，每种物品不是无限的，可能在w位置，图中椭圆圈出的位置代表着需要拿三个，但是如果规定最多拿两个，我们这种算法就出问题了。

一种做题思路：把每个物品都按01背包做：比如第i种物品，我们就按有p\[i\]件相同的物品。每一种物品都是如此，按01背包做就可以了。（但是显然很蠢）

改进：

我们平时买东西时，难道带的全是一元的硬币吗？当然不是，只要手中的钱可以凑出商品的价格即可，比如9元的东西，我不一定用九个硬币（背包问题的物品）来付钱，可以5元+4个1元。

背包问题也一样，我们不一定要全部拆成1的物品，只要我们的物品可以代表0——>p\[i\]的所有情况，我们就认为这种策略是正确的。

那如何拆p\[i\]个物品可以保证我们的物品可以代表0——>p\[i\]的所有情况呢？这里要借助2进制思想。

一个n位的二进制数可以取0到2的n次方-1，第i位代表的是2的i-1次方。

对应到物品：

我们的p\[i\]=15，我们怎样拆呢？

1+2+4+8即可，这四个数一定可以组合出0-15的任何一个数。

二进制拆分代码如下：

for (int i = 1; i <= n; i++) \{

int num = min(p\[i\], V / w\[i\]);

for (int k = 1; num > 0; k <<= 1) \{

if (k > num) k = num;

num -= k;

for (int j = V; j >= w\[i\] \* k; j--)

f\[j\] = max(f\[j\], f\[j - w\[i\] \* k\] + v\[i\] \* k);

## 3.4 一些变形选讲 ##

1）最常见的一些变形，甚至不能说是变形，上面也提到过，但是怕同学们不知道：

我们常见的问题中，一般是问最优解，可能是最大，或者最小，但是，问题也可能是方法的数量，这个时候，一般把状态转移方程中的max(min)改为sum（求和）即可，当然，压缩空间后的样子还是需要自己写。

2）初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求"恰好装满背包"时的最优解，有的题目则并没有要求必须把背包装满。这两种问法的区别是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f\[0\]为0其它f\[1...V\]均设为−∞，这样就可以保证最终得到的f\[N\]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f\[0...V\]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是

−∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

3）常数优化

前面的代码中有for(j=V...w\[i\])，还可以将这个循环的下限进行改进。

由于只需要最后f\[j\]的值，倒推前一个物品，其实只要知道f\[j−w\[n\]\]即可。以此类推，对以第j个背包，其实只需要知道到f\[j−sumw\[j...n\]\]即可，代码自行修改。

4）其实拆解二进制物品并不是多重背包的最优解，但是最优的单调队列思想写起来有些繁琐，可能以后会写。

# 可以刷的题 #

鉴于有一些同学说简单，我把去年写的一些题解放在这里：

[背包是否装满][Link 1]

[单调栈][Link 2]

[单调双端队列][Link 3]

[双端队列优化的背包问题][Link 4]

[字符串上的动态规划][Link 5]

[皇后问题][Link 6]（位运算）

[旅行商问题][Link 7]（认识状态压缩）

[蓝桥杯 摔手机 费时巨多的题解][Link 8]

[2018hbcpc dp总结 ][2018hbcpc dp_]

[HDU1029 HDU1087 HDU1176 HDU1257 POJ1458][HDU1029 HDU1087 HDU1176_HDU1257 POJ1458]

[POJ2533 HDU1114 HDU1260 HDU1160][]

[HDU1069 POJ3616 POJ1088][]

[POJ1189 UVA12511 HDU2845 HBCPC2018 K][]

[leetcode516 最长回文子序列][leetcode516]

[leetcode104 二叉树的最大深度][leetcode104]

[leetcode403 青蛙过河][leetcode403]

[leetcode115 不同的子序列][leetcode115]

[leetcode32 最长有效括号][leetcode32]

[leetcode 152 乘积最大子序列][leetcode 152]

[leetcode221 最大正方形][leetcode221]

[leetcode213 打家劫舍II][leetcode213 _II]

[leetcode97 交错字符串][leetcode97]

[leetcode542 01矩阵][leetcode542 01]

[leetcode303 区域和检索][leetcode303]

[leetcode72 编辑距离][leetcode72]

[leetcode45 跳跃游戏II 秒杀所有答案][leetcode45 _II]

[leetcode55 跳跃游戏 秒杀所有答案][leetcode55 _]

[leetcode63 不同路径II][leetcode63 _II]

[leecode5 最长回文子串][leecode5]

[leetcode300 最长上升子序列][leetcode300]

[leetcode64 最小路径和][leetcode64]

[leecode53 最大子序列和][leecode53]

[leecode11 盛水最多的容器][leecode11]

[leetcode538 把二叉搜索树转换成累加树][leetcode538]

[leetcode322 零钱兑换][leetcode322]

[leetcode70 爬楼梯][leetcode70]

[leetcode121买卖股票的最佳时机][leetcode121]

[https_img-blog.csdn.net_20180412131244538]: https://img-blog.csdn.net/20180412131244538
[20190906185552723.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1242fe09fe8247439a4841b5667c076d.png
[20190906185640844.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6c4b989842cc4488ad57d8ee488e6c07.png
[20190906185655908.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0f926bdefa2446cb9785660d30cd4574.png
[2019090618570111.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d06c91611b454f86b1454932668aea64.png
[20190906185823196.png]: https://img-blog.csdnimg.cn/20190906185823196.png
[2019090618582942.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1e6e364c821a452091713e98655712d4.png
[20190906185835607.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/48e75bb45e9a445290ec053333e13b37.png
[20190906185903993.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/80223b796f2644fda20b9bd3e63ca721.png
[20190906185915775.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/961da7d401714188994d9e7e52e8bbfd.png
[20190906185926488.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c7ad4052abf34e6e9c9d8a034bd0a883.png
[20190906190015908.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ed37654c65ae4371b4fb966b27a5229c.png
[20190906190027990.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9b4adfa0fc904572ad95bc0f1e4d1436.png
[20190906190044145.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/63f4733cb24941d8a98b755938d10cf8.png
[20190906190058210.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/675f8c8246fa40038664b6a32127f7f0.png
[20190906190115903.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1dfbb99d5d3042a29ecbfaea4ff5cd8a.png
[20190906190126337.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/95a4023431984cee9a6651de2fcd6aa9.png
[20190906190135593.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6f139022669f4978905f354cdc963a49.png
[https_img-blog.csdn.net_20180506110603122]: https://img-blog.csdn.net/20180506110603122
[2019090619015848.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2ddc18b06c894b669fc97f0b00e1034e.png
[20190906190210796.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/20501195fb4e4d15968627d93ec94d8a.png
[2019090619030419.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5aa1f86ea83f4519806f3c5b339d89da.png
[20190906190224227.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ac457ad2a8ce4ec4988d840123decdec.png
[2019090619031338.png]: https://img-blog.csdnimg.cn/2019090619031338.png
[2019090619031868.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c43e0117f4884d3e95c0e538f6e97fad.png
[20190906190332507.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/85e2652be5df4b97a098830e1ad3f2b5.png
[20190906190346828.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/591f127224c84e29838e67ee4bd30527.png
[20190906190420422.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a20930fc340045a785ea011a03156f56.png
[20190906190410550.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5ecd6b16582e414a9cb91d6983e0ab40.png
[Link 1]: https://blog.csdn.net/hebtu666/article/details/81781734
[Link 2]: https://blog.csdn.net/hebtu666/article/details/82717317
[Link 3]: https://blog.csdn.net/hebtu666/article/details/82720880
[Link 4]: https://blog.csdn.net/hebtu666/article/details/83018230
[Link 5]: https://blog.csdn.net/hebtu666/article/details/82687245
[Link 6]: https://blog.csdn.net/hebtu666/article/details/84631083
[Link 7]: https://blog.csdn.net/hebtu666/article/details/84988118
[Link 8]: https://blog.csdn.net/hebtu666/article/details/84789853
[2018hbcpc dp_]: https://blog.csdn.net/hebtu666/article/details/80402820
[HDU1029 HDU1087 HDU1176_HDU1257 POJ1458]: https://blog.csdn.net/hebtu666/article/details/81390118
[POJ2533 HDU1114 HDU1260 HDU1160]: https://blog.csdn.net/hebtu666/article/details/81393716
[HDU1069 POJ3616 POJ1088]: https://blog.csdn.net/hebtu666/article/details/81811310
[POJ1189 UVA12511 HDU2845 HBCPC2018 K]: https://blog.csdn.net/hebtu666/article/details/81837461
[leetcode516]: https://blog.csdn.net/hebtu666/article/details/103375511
[leetcode104]: https://blog.csdn.net/hebtu666/article/details/103318054
[leetcode403]: https://blog.csdn.net/hebtu666/article/details/103326247
[leetcode115]: https://blog.csdn.net/hebtu666/article/details/103326128
[leetcode32]: https://blog.csdn.net/hebtu666/article/details/103326023
[leetcode 152]: https://blog.csdn.net/hebtu666/article/details/103298823
[leetcode221]: https://blog.csdn.net/hebtu666/article/details/103277586
[leetcode213 _II]: https://blog.csdn.net/hebtu666/article/details/103277328
[leetcode97]: https://blog.csdn.net/hebtu666/article/details/103257370
[leetcode542 01]: https://blog.csdn.net/hebtu666/article/details/103252643
[leetcode303]: https://blog.csdn.net/hebtu666/article/details/103251383
[leetcode72]: https://blog.csdn.net/hebtu666/article/details/103251061
[leetcode45 _II]: https://blog.csdn.net/hebtu666/article/details/103250760
[leetcode55 _]: https://blog.csdn.net/hebtu666/article/details/103249983
[leetcode63 _II]: https://blog.csdn.net/hebtu666/article/details/103249814
[leecode5]: https://blog.csdn.net/hebtu666/article/details/103249571
[leetcode300]: https://blog.csdn.net/hebtu666/article/details/103246161
[leetcode64]: https://blog.csdn.net/hebtu666/article/details/103245662
[leecode53]: https://blog.csdn.net/hebtu666/article/details/103245202
[leecode11]: https://blog.csdn.net/hebtu666/article/details/103244211
[leetcode538]: https://blog.csdn.net/hebtu666/article/details/103201864
[leetcode322]: https://blog.csdn.net/hebtu666/article/details/103201591
[leetcode70]: https://blog.csdn.net/hebtu666/article/details/103201337
[leetcode121]: https://blog.csdn.net/hebtu666/article/details/103171757