在我们LeetCode刷题过程中，如果我们只是了解数据结构（数组，链表，数）的使用方法，那我们在面对复杂的题目时，是很难很好的解决问题的，因此我们要了解一些常用算法来帮助我们更好的解题。

递归和迭代

递归

在高级语言中，调用自己和其它函数没有本质的不同。我们把一个直接用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。每个递归函数必须至少有一个条件，满足时递归不再执行，即不再引用自身而是返回值退出。

​ 简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

递归的两个必要条件
1、存在限制条件，当满足这个条件时，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。

如下简单示例，我们求一个数n的阶乘：

f(n) = n*(n-1)*(n-2) … 21

显然，该式子还可以写成：

f(n) = n*f(n-1)

因为f(n)与f(n-1)有关系，即基于其子问题，于是便可以采用“递归”求解。

Python代码：

def func(self, n):
   if n == 1:
       return 1
   else:
       return n * self.func(n - 1)

可视化直观表示即：

可视化直观表示即：

​ 递归其实可以看做两部分操作，一步步去寻求子问题的解（直到满足限制条件，如n==1，得f(1)=1）是“递”；得到最基本的子问题的解之后，再一步步返回求上一层的解是“归”。

（如上图，“递”的过程中，f(n)=n*f(n-1)，结果值都是基于子问题的；但是，到最基本的问题之后，得到了解，“归”的过程中，每一步都有确定的返回值，直到一层层返回结束，得解。）

因为，函数的递归要利用到“栈”，下图以“栈”的方式展现“递归”过程：

​ “递”的过程会将函数的地址、参数等压栈（push）保存（以便“归”的时候找到之前执行到的位置），最基本子问题（f(1)=1）求解之后，再一步步“归”，此过程中，会发生出栈（pop）操作，函数调用结束后，栈顶释放。

将两个过程用函数打印出来看一下：

def func(n):
    print "递：%d "%n,
    if n==1:
        res = 1
    else:
        res = n*func(n-1)
    print "归:%d "%res,
    return res

func(4)

结果：

超简洁图解
如果上述两个图示还不够清晰的话，请看第三个：

我们将函数的递归调用看做微机原理中的“中断响应”;

假如图中“圆环”代表print，且其位于递归调用之后(类似中断响应的断点之后)，那么最后调用的反而最先print！（根据函数的执行流程，即图中的箭头方向） [类似于栈LIFO].

如打印一个链表：

# 递归打印链表
def printListNode(self,lst):
    if not lst:
        return
    # print lst.val,
    self.printListNode(lst.next)
    print lst.val,

print在递归调用之后，则结果(假如单向无环链表[1,2,3,4])：

（如果print在断点之前，则完全相反！）

# 递归打印链表
def printListNode(self,lst):
    if not lst:
        return
    print lst.val,
    self.printListNode(lst.next)
    # print lst.val,

print在递归调用之后，则结果(假如单向无环链表[1,2,3,4])：

附：二叉树的先序、中序、后序遍历之所以得到那样的结果，也是因函数中print的位置在调用递归的前后位置不同造成的。

迭代

迭代法也称辗转法，是一种不断用变量的旧值推出新值的过程。它是解决问题的一种基本方法，通过让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

迭代算法的基本思想是：为求一个问题的解x，可由给定的一个初值x0，根据某一迭代公式得到一个新的值x1，这个新值x1比初值x0更接近要求的值x；再以新值作为初值，即：x1→x0，重新按原来的方法求x1，重复这一过程直到|x1-x0|<ε(某一给定的精度)。此时可将x1作为问题的解x。

利用迭代算法解决问题，需要做好以下三个方面的工作：

（1）确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值推出新值的变量，这个变量就是迭代变量。

（2）建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键。

（3）对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

迭代也是用循环结构实现，只不过要重复的操作是不断从一个变量的旧值出发计算它的新值。其基本格式描述如下：

迭代变量赋初值；

while (迭代终止条件)

{

根据迭代表达式，由旧值计算出新值；

新值取代旧值，为下一次迭代做准备；

}

迭代的经典例子
1.斐波那契数列（没错，又是我）
2.汉诺塔问题（这不巧了么）
3.背包问题
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。
可以压缩空间，f[v]=max{f[v],f[v-w[i]]+v[i]}
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”，此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。
注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为f[v]。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0…V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。
同样的例子，做法不同，也就有了不同的定义
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

迭代和递归的关系和区别（敲黑板）

从概念上讲，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。简单地说，递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环，而迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。
递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)。
在循环的次数较大的时候，迭代的效率明显高于递归。
以斐波那契数列的求解为例，通过两种典型的实现进行对比：
递归的实现

int fib(int n){  
         if(n>1) return fib(n-1) + fib(n-2);  
         else return n; // n = 0, 1时给出recursion终止条件  
    }  

迭代

int fib(int n){  
    int i, temp0, temp1, temp2;        
    if(n<=1) return n;  
    temp1 = 0;  
    temp2 = 1;  
    for(i = 2; i <= n; i++){  
        temp0 = temp1 + temp2;  
        temp2 = temp1;  
        temp1 = temp0;  
    }  
    return temp0;  
} 

二分法

对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

典型的二分法

算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。

基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，

如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；

若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，

直到找到为止,时间复杂度:O(log(n))。

以后大家只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下表可能不是唯一的。

C语言代码实现

int search(int *arr, int n, int key)
{
    int left = 0, right = n-1;
    while(left<=right) {//慎重截止条件，根据指针移动条件来看，这里需要将数组判断到空为止
        int mid = left + ((right - left) >> 1);//防止溢出
        if (arr[mid] == key)//找到了
            return mid; 
        else if(arr[mid] > key) 
            right = mid - 1;//给定值key一定在左边，并且不包括当前这个中间值
        else 
            left = mid + 1;//给定值key一定在右边，并且不包括当前这个中间值
    }
    return -1;
}

C++代码实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1; // 我们定义target在左闭右闭的区间里，[left, right]，这个区间的定义就是我们的不变量，接下来，要在下面的循环中，坚持这个不变量，我们就知道其中的边界条件应该怎么判断了
        while (left <= right) { // 为什么是<=呢，因为当left==right，区间[left, right]依然有效
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，因为我们的区间是左闭右闭的区间，nums[middle]一定不是我们的目标值，所以在right = middle - 1在[left, middle - 1]区间中继续寻找目标值
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前，此时区间为[0, -1]，所以return right + 1
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置，一定是我们查找的范围 [left, right]之后，return  right + 1
        // 目标值在数组所有元素之后的情况，也是我们查找的范围 [left, right]之后， return right + 1
        return right + 1;
    }
};

证明二分算法正确性：
循环不变式：
如果key存在于数组中，始终只可能存在于当前的array[left,right]数组段中。

初始化：
　　第一轮循环开始之前，array[left,right]就是原始数组，这时循环不变式显然成立。

迭代保持：

每次循环开始前，如果key存在，则只可能在待处理数组array[left, …, right]中。

对于array[mid]<key，array[left, …, mid]均小于key，key只可能存在于array[mid+1, …, right]中；
　　对于array[mid]>key，array[mid, …, right]均大于key，key只可能存在于array[left, …, mid-1]中；
　　对于array[mid]key，查找到了key对应的下标，直接返回结果。
显然如果没找到key，下一次继续查找时我们设定的循环不变式依然正确。
　 死循环否？在前两种情况中，数组长度每次至少减少1（实际减少的长度分别是mid-left+1和right-mid+1），直到由leftright变为left>right（数组段长度由1-0）—>截止了，所以一定不会死循环。

终止：
　　结束时发生了什么？left>right,被压缩的数组段为空，表示key不存在于所有步骤的待处理数组，再结合每一步排除的部分数组中也不可能有key，因此key不存在于原数组。因此我们得到了符合要求的解，此算法正确。

如果说我们定义 target 是在一个在左闭右开的区间里，也就是[left, right)

那么二分法的边界处理方式则截然不同。

不变量是[left, right)的区间，如下代码可以看出是如何在循环中坚持不变量的。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n; // 我们定义target在左闭右开的区间里，[left, right)  这是
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，因为是左闭右开的区间，nums[middle]一定不是我们的目标值，所以right = middle，在[left, middle)中继续寻找目标值
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在 [middle+1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值的情况，直接返回下标
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前，此时区间为 [0,0)，所以可以return right
        // 目标值等于数组中某一个元素 return middle
        // 目标值插入数组中的位置 [left, right) ，return right 即可
        // 目标值在数组所有元素之后的情况 [left, right)，return right 即可
        return right;
    }
};

从上面两种二分法的代码中，我们可以看到是如何处理二分查找过程中的边界情况

很多同学二分写不好，就是因为边界总是不知道 该是<= 还是< 呢，

是 right = middle - 1呢 还是 right = middle呢

这都是因为没有意识到去区间的定义，区间的定义就是我们的不变量

在二分部查找的过程只要遵循着区间的定义也就是这个不变量

我们就可以很轻松的写出二分法

以上讲解大家应该对二分法中循环不变量有一个直观的感受

理解的查找区间的定义（不变量），然后在二分循环中遇到了不知该如何处理的边界条件的时候

就去想一下 我们区间的定义，这样就知道边界条件应该如何去写了

二分法的变种

数组之中的数据可能可以重复，要求返回匹配的数据的最小（或最大）的下标；更近一步， 需要找出数组中第一个大于key的元素（也就是最小的大于key的元素的）下标，等等。 这些，虽然只有一点点的变化，实现的时候确实要更加的细心。

下面列出了这些二分检索变种的实现

找出第一个与key相等的元素的位置

快速思考四个问题：

1）通过什么条件来移动两个指针？与中间位置进行大小比较。

当arr[mid]<key时，当前位置一定不是解，解一定只可能在arr[mid+1,high]，即右边

当arr[mid]>key时，当前位置一定不是解，解一定只可能在arr[low,mid-1]，即左边

当arr[mid]==key呢？mid有可能是解，也可能在arr[low,mid-1]即左边,但可以肯定的是解一定只可能在arr[low,mid]中。

2）两个指针的意义？缩小范围，如果key存在于数组中，最终将low移动到目的位置。

3）程序的出口？截止条件就是出口，唯一的出口。

4）那截止条件应该如何写？这得看怎么移动的！

int searchFirstEqual(int *arr, int n, int key)
{
    int left = 0, right = n-1;
    while(left < right)//根据两指针的意义，如果key存在于数组，left==right相等时已经得到解
    {
        int mid = (left+right)/2;
        if(arr[mid] > key)//一定在mid为止的左边，并且不包含当前位置
            right = mid - 1;
        else if(arr[mid] < key) 
            left = mid + 1;//一定在mid位置的右边，并且不包括当前mid位置
        else
            right=mid;//故意写得和参考博文不一样，下面有证明
    }
    if(arr[left] == key) 
            return left;
    return -1;
}

证明变种二分a的正确性：

循环不变式：
　　如果key存在于数组，那么key第一次出现的下标x只可能在[left,right]中，并且始终有array[left]<=key, array[right]>=key

初始化：
　　第一轮循环开始之前，数组段就是原数组，这时循环不变式显然成立。

迭代保持：
　　每次循环开始前，如果key存在于原数组，那么位置x只可能存在于待查找数组array[left, …, right]中。
　　如果array[mid]<key，array[left, …, mid]均小于key，x只可能存在于array[mid+1, …, right]中。数组减少的长度为mid-left+1，至少为1。
　　如果array[mid]>key, array[mid, …, right]均大于key的元素，x只可能存在于array[left, …, mid-1]中.数组减少的长度为right-mid+1，至少为1。
对于array[mid]==key, array[mid, …, right]均大于或者等于key的元素，x只可能存在于array[left, …, mid]中，这里长度减少多少呢？见下面死循环分析。

显然迭代过程始终保持了循环不变式的性质。

死循环否？前两个条件至少减少1，但是后一个条件当两个指针的相距为2及其以上时（比如2->5，距离为2）

长度至少减少1，然而当相距为1时将无法减少长度，但是聪明的我们将其截止了，所以不会出现死循环。

终止：

​ 结束时发生了什么？即leftright时，根据循环不变式始终有array[left]<=key, array[right]>=key（否则就不应该在这里找）。显然我们把两个指针缩小到leftright的情况，只要检查array[left]==key即可得到满足问题的解。因此算法是正确的。

找出最后一个与key相等的元素的位置

int searchLastEqual(int *arr, int n, int key)
{
    int left = 0, right = n-1;
    while(left<right-1) {
        int mid = (left+right)/2;
        if(arr[mid] > key) 
            right = mid - 1;//key一定在mid位置的左边，并且不包括当前mid位置
        else if(arr[mid] < key) 
            left = mid + 1; //key一定在mid位置的右边，相等时答案有可能是当前mid位置
        else
            left=mid;//故意写得和参考博客不一样，见下面证明
    }
    if( arr[left]<=key && arr[right] == key) 
        return right;
    if( arr[left] == key && arr[right] > key)
        return left;
    return -1;
}

循环不变式：

如果key存在于数组，那么key最后一次出现的下标x只可能在[left,right]中，并且和上一题一样始终有array[left]<=key, array[right]>=key

初始化：
　　第一轮循环开始之前，数组段就是原数组，这时循环不变式显然成立。

迭代保持：
　　每次循环开始前，如果key存在于原数组，那么位置x只可能存在于待查找数组array[left, …, right]中。
　　如果array[mid]<key，array[left, …, mid]均小于key，x只可能存在于array[mid+1, …, right]中。数组减少的长度为mid-left+1，至少为1。
　　如果array[mid]>key, array[mid, …, right]均大于key的元素，x只可能存在于array[left, …, mid-1]中.数组减少的长度为right-mid+1，至少为1。
对于array[mid]==key, array[mid, …, right]均大于或者等于key的元素，x只可能存在于array[mid, …,right]中，长度减少情况见下面死循环分析。

迭代过程始终保持了循环不变式。

死循环否？前两个条件至少减少1，但是后一个条件当两个指针的相距为3及其以上时（比如2->5->7，距离为3）

长度至少减少1，然而当相距为2时将无法减少长度，但是聪明的我们利用left<right-1将其截止了，所以不会出现死循环。

终止：

​ 结束时发生了什么？即left==right-1时，根据循环不变式始终有array[left]<=key, array[right]>=key（否则就不应该在这里找）。显然我们把两个指针缩小到只有left和right两个情况，只要检查两个位置的值与key相等与否即可得到满足问题的解。因此算法是正确的。

以上两个算法尽管参考别人博客，但是证明以及具体二分写法都不一样，可以仔细对比学习。

查找第一个等于或者大于Key的元素的位置

int searchFirstEqualOrLarger(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) 
    {
        int mid = (left+right)/2;
        if(arr[mid] >= key) 
            right = mid-1;
        else if (arr[mid] < key) 
            left = mid+1;
    }
    return left;
}

查找第一个大于key的元素的位置

int searchFirstLarger(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right)
    {
        int mid = (left+right)/2;
        if(arr[mid] > key) 
            right = mid-1;
        else if (arr[mid] <= key) 
            left = mid+1;
    }
    return left;
}

查找最后一个等于或者小于key的元素的位置

int searchLastEqualOrSmaller(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) 
    {
        int m = (left+right)/2;
        if(arr[m] > key) 
             right = m-1;
        else if (arr[m] <= key) 
             left = m+1;
    }
    return right;
}

查找最后一个小于key的元素的位置

int searchLastSmaller(int *arr, int n, int key)
{
    int left=0, right=n-1;
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid] >= key) 
             right = mid-1;
        else if (arr[mid] < key) 
             left = mid+1;
    }
    return right;
}

下面是一个测试的例子：

int main(void) 
{
    int arr[17] = {1, 
                   2, 2, 5, 5, 5, 
                   5, 5, 5, 5, 5, 
                   5, 5, 6, 6, 7};
    printf("First Equal           : %2d \n", searchFirstEqual(arr, 16, 5));
    printf("Last Equal            : %2d \n", searchLastEqual(arr, 16, 5));
    printf("First Equal or Larger : %2d \n", searchFirstEqualOrLarger(arr, 16, 5));
    printf("First Larger          : %2d \n", searchFirstLarger(arr, 16, 5));
    printf("Last Equal or Smaller : %2d \n", searchLastEqualOrSmaller(arr, 16, 5));
    printf("Last Smaller          : %2d \n", searchLastSmaller(arr, 16, 5));
    system("pause");
    return 0;
}

最后输出结果是：
First Equal : 3
Last Equal : 12
First Equal or Larger : 3
First Larger : 13
Last Equal or Smaller : 12
Last Smaller : 2
很多的时候，应用二分检索的地方都不是直接的查找和key相等的元素，而是使用上面提到的二分检索的各个变种，熟练掌握了这些变种，当你再次使用二分检索的检索的时候就会感觉的更加的得心应手了。

二分法总结

二分法的代码中是存在非常多的细节的，一不小心，我们写出来的二分法就会存在bug。

下面我们以LeetCode上的一道二分法的题目来看看。

正确解答代码如下

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while(low <= high){
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
};

容易出错的地方1：终止条件

while(low <= high) 如果写成了 while(low < high)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while(low < high){ //修改
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
};

那执行会报错

int low = 0, high = nums.size() - 1;

while(low < high)

当数组只有一个元素，则 low = 0, high = 1 -1 = 0，又因为while(low < high)。

所以根本就不会进入循环，也就根本没有执行判断。

那我们把high = nums.size() - 1改成high = nums.size() 可以吗？

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size();//修改
        while(low < high){ 
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
};

low=0，high=6

第一次循环：mid=3 ，nums[mid] = 5 < 9，low = mid + 1 = 4

第二次循环：mid=(4+6)/2=5 ，nums[mid] = 12 > 9，high = mid - 1 = 4

此时 low和mid都是等于4，加上while(low < high)，循环终止，没找到目标值。

当然，如果我们同时将

high = nums.size()

while(low <= high)

那代码可以通过测试

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size();//修改
        while(low <= high){ 
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
};

通过上面我们也可以知道high = nums.size()或者high = nums.size()-1都是可以的。

容易出错的地方2：high的取值判断

将high = mid - 1变成high = mid

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while(low <= high){
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
};

这种显示超出时间限制那就是应该就是一直在进行循环，导致超时。

low=0，high=5

第一次循环：mid=2 ，nums[mid] = 3 > 2，high = mid = 2

第二次循环：mid=(0+2)/2=1 ，nums[mid] = 0 < 2，low = mid + 1 = 2

后面循环：因为low=high=2，而且while(low <= high)，因此该循环就变成了死循环就会导致超时。

所以我们可以针对可能会进入死循环设置一个退出条件。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        int count = 0;
        while(low <= high){
            count++;
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid;
            } else {
                low = mid + 1;
            }

            if (count >= nums.size())
            {
                return -1;
            }
        }
        return -1;
    }
};

当然上面这种解决方法不优雅，也不利于我们加深对二分法的使用，因此我们不建议使用该种方法。

我们还是继续分析上面的情况，进入死循环的原因是while(low <= high)中是小于等于，那我们改成小于不就解决了吗？

改成下面的代码之后

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;

        while(low < high){

            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid;
            } else {
                low = mid + 1;
            }

        }
        return -1;
    }
};

当数组只有一个元素，则 low = 0, high = 1 -1 = 0，又因为while(low < high)。

所以根本就不会进入循环，也就根本没有执行判断。

因此我们将high = nums.size()-1改成high = nums.size()。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size();

        while(low < high){

            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid;
            } else {
                low = mid + 1;
            }

        }
        return -1;
    }
};

代码可以成功执行。

容易出错的地方3：low的取值判断

将low = mid-1改成low = mid

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;

        while(low <= high){

            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid-1;
            } else {
                low = mid;
            }

        }
        return -1;
    }
};

low=0，high=6

第一次循环：mid=3 ，nums[mid] = 5 > 2，high = mid - 1 = 2

第二次循环：mid=(0+2)/2=1 ，nums[mid] = 0 < 2，low = mid = 1

第三次循环：mid=(1+2)/2=1 ，nums[mid] = 0 < 2，low = mid = 1

第四次循环：mid=(1+2)/2=1 ，nums[mid] = 0 < 2，low = mid = 1

、、、

可以看出就这样会一直无限循环，这边的无限循环不是因为 low和high相等造成的，而是因为low = mid，而mid=(low+high)/2=low，而high比low和mid大1造成的。

---

从上面的可以看出，写二分法要非常注意边界条件，一个等号，一个+1都可能让程序产生不同的效果，因为我们要牢牢把握住标准解法，然后在标准解法的基础上进行变通。

双指针法(尺取法)

双指针技巧可以分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。

尺取法其实是一个降低复杂度的优化算法，废话不多说，先上一道题。

题目：给定一个数组和一个数s，在这个数组中找一个区间，使得这个区间之和等于s。

例如：给定的数组int x[14] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};和一个s = 15。那么，可以找到的区间就应该有0到4， 3到5， 6到7.（注意这里的下标从0开始）

对于这样的题，不用任何技巧就可以跑出结果，例如下面这个方法可能是大多数人能够想出来的：

先用一个数组sum[i]存放前i个元素的和，其实现用的是”递推思想“，注意，在编程中”递推“的思想用的特别多，一定要习惯这种思维方式。

sum[0] = x[0];//x为给定的原数组
for(int i = 1; i < n; i++){
   sum[i] += sum[i-1];//递推思想
}

然后通过两层循环求解

for(int i = 0; i < n; i++)
	for(int j = n-1; j >= 0; j--){
		if(sum[j]-sum[i]==s)	printf("%d---%d\n", i, j);
	}

上面的方法当然是可行的，但是复杂度太高，有一个算法可以将其复杂度降为O(n)。这就是”尺取算法“。

尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的。

那么，用”尺取法“做上面这道题思路应该是这样的：

其实，这种方法很类似于蚯蚓的蠕动。

1）用一对脚标i, j。最开始都指向第一个元素。

2）如果区间i到j之和比s小，就让j往后挪一位，并把sum的值加上这个新元素。相当于蚯蚓的头向前伸了一下。

3）如果区间i到j之和比s大，就让sum减掉第一个元素。相当于蚯蚓的尾巴向前缩了一下。

4）如果i到j之和刚好等于s，则输入。

用一张图来表示就是这样的，每一行的黄色部分代表本次循环选中的区间

接下来附上完整源代码：

#include<iostream>
#include<cstdio>
using namespace std;
 
void findSUM(int *A, int n, int s){
	int i = 0, j = 0;
	int sum = A[0];
	while(i <= j && j < n){
		if(sum >= s){
			if(sum == s)	printf("%d---%d\n", i, j);
			sum -= A[i];
			i++;
		}
		else{
			j++;
			sum += A[j];
		}
	}
} 
 
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int m;
    int x[14] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    cin >> m;
    findSUM(x, 14, m);
 
	return 0;
}

大家可以看到，”尺取法“一般只有O（n）的复杂度，针对大规模数据还是很有效的。另外，”尺取法“有时候也叫“双指针法”，当然，名字并没有那么重要，领会思想就行。

一、快慢指针的常见算法

快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

1、判定链表中是否含有环

单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。

如果链表中不含环，那么这个指针最终会遇到空指针 null 表示链表到头了，这还好说，可以判断该链表不含环。

public boolean hasCycle(ListNode head) {
    while (head != null){
        head = head.next;
    }
    return false;
}

但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有 null 指针作为尾部节点。

经典解法就是用两个指针，一个每次前进两步，一个每次前进一步。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

public boolean hasCycle(ListNode head){
    ListNode fast, slow;
    fast = slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}

2、已知链表中含有环，返回这个环的起始位置

public static ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode index1 = fast;
                ListNode index2 = head;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index2;
            }
        }
        return null;
    }

3、寻找链表的中点

类似上面的思路，我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

public static ListNode findMid(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;// slow 就在中间位置
}    

当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右。

寻找链表中点的一个重要作用是对链表进行归并排序。

回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。对于链表，合并两个有序链表是很简单的，难点就在于二分。

但是现在你学会了找到链表的中点，就能实现链表的二分了。

4、寻找链表的倒数第 k 个元素

我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）：

public static ListNode findK(ListNode head, int k) {
    ListNode slow, fast;
    slow = fast = head;
    while (k-- > 0){
        fast = fast.next;
    } 
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

应用比如：力扣第 19 题「删除链表的倒数第n个元素」

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        if(fast == null){// 如果此时快指针走到头了，说明倒数第 n 个节点就是第一个结点
            return head.next;
        }
        while(fast != null && fast.next != null){// 让慢指针和快指针同步向前
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;// slow.next 就是倒数第 n 个节点，删除它
        return head;
    }
}

二、左右指针的常用算法

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

1、二分查找

前文 二分查找算法详解 有详细讲解，这里只写最简单的二分算法，旨在突出它的双指针特性：

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
        }
    return -1;
}

2、两数之和

直接看一道 LeetCode 题目吧：

只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 可以调整 sum 的大小：

int twoSum(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    while(left < right) {
        int sum = nums[left] + nums[right];
        if(sum == target)
            return new int[]{left + 1, right + 1}; 
        else if (sum < target)
            left++;
        else if (sum > target)
            right--;
        }
    return -1;
}

3、反转数组

public void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

4、滑动窗口算法

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

其中两处…表示的更新窗口数据的地方，到时候直接往里面填就行了。

而且，这两个…处的操作分别是右移和左移窗口更新操作，等会你会发现它们操作是完全对称的。

注:把索引左闭右开区间[left, right)称为一个窗口。

滑动窗口

滑动窗口实际上也是双指针的应用，滑动窗口的右指针不断扩大窗口的范围，当窗口内的对象符合某个条件时，进行统计或者某种操作；然后左指针收缩窗口来打破条件，以便让右指针右移继续扩大窗口

209 长度最小的子数组

使用左右指针来构建一个滑动窗，
当窗口内的数字的和<s时，右指针右移来扩大窗口；
当窗口内的数字之和>=s时,统计窗口的长度，并将左指针右移来缩小窗口

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0 
        i, j = 0, 0 
        windowSum = 0
        min_len = float('inf')
        while j<len(nums):       
            windowSum += nums[j]
            while i<=j and windowSum>=s:
                min_len = min(min_len, j-i+1)
                windowSum -= nums[i]
                i+=1
            j+=1

        return 0 if min_len == float('inf') else min_len

贪心算法（贪婪算法）

先来看看维基百科的定义：

贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况，选择最优的解，可能会导致辛普森悖论（Simpson’s Paradox），不一定出现最优的解。

贪心算法在数据科学领域被广泛应用，特别是金融工程。其中一个贪心算法例子就是Ensemble method。

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。}

贪婪法的基本步骤：

步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。

事例一：找零钱问题

假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？

这里需要明确的几个点：
1.货币只有 25 分、10 分、5 分和 1 分四种硬币；
2.找给客户 41 分钱的硬币；
3.硬币最少化

思考，能使用我们今天学到的贪婪算法吗？怎么做？

（回顾一下上文贪婪法的基本步骤，1，2，3）

1.找给顾客sum_money=41分钱，可选择的是25 分、10 分、5 分和 1 分四种硬币。能找25分的，不找10分的原则，初次先找给顾客25分；
2.还差顾客sum_money=41-25=16。然后从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束；
3.此时41分，分成了1个25，1个10，1个5，1个1，共四枚硬币。

编程实现

#include<iostream>
using namespace std;

#define ONEFEN    1
#define FIVEFEN    5
#define TENFEN    10
#define TWENTYFINEFEN 25

int main()
{
    int sum_money=41;
    int num_25=0,num_10=0,num_5=0,num_1=0;

    //不断尝试每一种硬币
    while(money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; }
    while(money>=TENFEN) { num_10++; sum_money -=TENFEN; }
    while(money>=FIVEFEN)  { num_5++;  sum_money -=FIVEFEN; }
    while(money>=ONEFEN)  { num_1++;  sum_money -=ONEFEN; }

    //输出结果
    cout<< "25分硬币数："<<num_25<<endl;
    cout<< "10分硬币数："<<num_10<<endl;
    cout<< "5分硬币数："<<num_5<<endl;
    cout<< "1分硬币数："<<num_1<<endl;

    return 0;
}

事例二:背包最大价值问题

有一个背包，最多能承载重量为 C=150的物品，现在有7个物品（物品不能分割成任意大小），编号为 1~7，重量分别是 wi=[35,30,60,50,40,10,25]，价值分别是 pi=[10,40,30,50,35,40,30]，现在从这 7 个物品中选择一个或多个装入背包，要求在物品总重量不超过 C 的前提下，所装入的物品总价值最高。

这里需要明确的几个点：
1.每个物品都有重量和价值两个属性；
2.每个物品分被选中和不被选中两个状态（后面还有个问题，待讨论）；
3.可选物品列表已知，背包总的承重量一定。

所以，构建描述每个物品的数据体结构 OBJECT和背包问题定义为：

//typedef是类型定义的意思

//定义待选物体的结构体类型
typedef struct tagObject
{
    int weight;
    int price;
    int status;
}OBJECT;

//定义背包问题
typedef struct tagKnapsackProblem
{
    vector<OBJECT>objs;
    int totalC;
}KNAPSACK_PROBLEM;

这里采用定义结构体的形式，主要是可以减少代码的书写量,可以实现代码的复用性和可扩展性,简化，提高可读性。就是贪图简单方便，规避繁琐。

如下,实例化objects

OBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },
                    { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };

思考：如何选，才使得装进背包的价值最大呢？

策略1：价值主导选择，每次都选价值最高的物品放进背包；
策略2：重量主导选择，每次都选择重量最轻的物品放进背包；
策略3：价值密度主导选择，每次选择都选价值/重量最高的物品放进背包。

（贪心法则：求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好的或最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好或最优的解）

策略1：价值主导选择，每次都选价值最高的物品放进背包

根据这个策略最终选择装入背包的物品编号依次是 4、2、6、5，此时包中物品总重量是 130，总价值是 165。

//遍历没有被选的objs,并且选择price最大的物品,返回被选物品的编号
int Choosefunc1(std::vector<OBJECT>& objs, int c)
{
    int index = -1;  //-1表示背包容量已满
    int max_price = 0;
    //在objs[i].status == 0的物品里，遍历挑选objs[i].price最大的物品
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if ((objs[i].status == 0) && (objs[i].price > max_price ))//objs没有被选,并且price> max_price 
        {
            max_price  = objs[i].price;
            index = i;
        }
    }

    return index;
}

策略2：重量主导选择，每次都选择重量最轻(小)的物品放进背包

根据这个策略最终选择装入背包的物品编号依次是 6、7、2、1、5，此时包中物品总重量是 140，总价值是 155。

int Choosefunc2(std::vector<OBJECT>& objs, int c)
{
    int index = -1;
    int min_weight= 10000;
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if ((objs[i].status == 0) && (objs[i].weight < min_weight))
        {
            min_weight= objs[i].weight;
            index = i;
        }
    }

    return index;
}

策略3：价值密度主导选择，每次选择都选价值/重量最高(大)的物品放进背包

物品的价值密度 si 定义为 pi/wi，这 7 件物品的价值密度分别为 si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]。根据这个策略最终选择装入背包的物品编号依次是 6、2、7、4、1，此时包中物品的总重量是 150，总价值是 170。

int Choosefunc3(std::vector<OBJECT>& objs, int c)
{
    int index = -1;
    double max_s = 0.0;
    for (int i = 0; i < static_cast<int>(objs.size()); i++)
    {
        if (objs[i].status == 0)
        {
            double si = objs[i].price;
            si = si / objs[i].weight;
            if (si > max_s)
            {
                max_s = si;
                index = i;
            }
        }
    }

    return index;
}

有了物品，有了方法，下面就是将两者结合起来的贪心算法GreedyAlgo

void GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc)
{
    int idx;
    int sum_weight_current = 0;
    //先选
    while ((idx = spFunc(problem->objs, problem->totalC- sum_weight_current)) != -1)
    {   //再检查，是否能装进去
        if ((sum_weight_current + problem->objs[idx].weight) <= problem->totalC)
        {
            problem->objs[idx].status = 1;//如果背包没有装满，还可以再装,标记下装进去的物品状态为1
            sum_weight_current += problem->objs[idx].weight;//把这个idx的物体的重量装进去，计算当前的重量
        }
        else
        {
            //不能选这个物品了，做个标记2后重新选剩下的
            problem->objs[idx].status = 2;
        }
    }
    PrintResult(problem->objs);//输出函数的定义，查看源代码
}

注意：这里对objs[idx].status定义了三种状态，分别是待选择为0（初始所有状态均为0），装进包里变为1，判断不符合变为2，这样最后只需要拿去状态为1的即可。

主函数部分

OBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },
                    { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };
int main()
{
    KNAPSACK_PROBLEM problem;

    problem.objs.assign(objects, objects + 7);//assign赋值，std::vector::assign
    problem.totalC = 150;

    cout << "Start to find the best way ,NOW" << endl;
    GreedyAlgo(&problem, Choosefunc3);

    system("pause");
    return 0;
}

查看策略3的输出结果：

但是，我们再回顾一下第一个事例问题

现在问题变了，还是需要找给顾客41分钱，现在的货币只有 25 分、20分、10 分、5 分和 1 分四种硬币；该怎么办？

按照贪心算法的三个步骤：

1.41分，局部最优化原则，先找给顾客25分；
2.此时，41-25=16分，还需要找给顾客10分，然后5分，然后1分；
3.最终，找给顾客一个25分，一个10分，一个5分，一个1分，共四枚硬币。

是不是觉得哪里不太对，如果给他2个20分，加一个1分，三枚硬币就可以了呢？^_;

总结：贪心算法的优缺点

优点：简单，高效，省去了为了找最优解可能需要穷举操作，通常作为其它算法的辅助算法来使用；

缺点：不从总体上考虑其它可能情况，每次选取局部最优解，不再进行回溯处理，所以很少情况下得到最优解。

完整代码：https://github.com/QianLingjun/

动态规划

0. intro

很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。恰好我给入门者讲过四次DP入门，迭代出了一套比较靠谱的教学方法，所以今天跑过来献丑。

现在，我们试着自己来一步步“重新发明”DP。

1. 从一个生活问题谈起

先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。

依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。

这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。

但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
　　15=1×11+4×1 （贪心策略使用了5张钞票）
　　15=3×5 （正确的策略，只用3张钞票）
　　为什么会这样呢？贪心策略错在了哪里？

鼠目寸光。
　　刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。
　　在这里我们发现，贪心是一种只考虑眼前情况的策略。

那么，现在我们怎样才能避免鼠目寸光呢？

如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。

重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。

那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
　　明显[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LN2ZpB1M-1631201859692)(https://www.zhihu.com/equation?tex=\text{cost}+%3D+f(4)]+%2B+1+%3D+4+%2B+1+%3D+5) ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。
　　依次类推，马上可以知道：如果我们用5来凑出15，cost就是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uhCl9Mrq-1631201859693)(https://www.zhihu.com/equation?tex=f(10)]+%2B+1+%3D+2+%2B+1+%3D+3) 。

那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！

• 取11：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kqgYyTk6-1631201859694)(https://www.zhihu.com/equation?tex=\text{cost}%3Df(4)]%2B1%3D4%2B1%3D5)
• 取5： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ndn1XT7G-1631201859694)(https://www.zhihu.com/equation?tex=\text{cost}%3Df(10)]%2B1%3D2%2B1%3D3)
• 取1： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TUEFe6kZ-1631201859695)(https://www.zhihu.com/equation?tex=\text{cost}%3Df(14)]%2B1%3D4%2B1%3D5)

显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！

这给了我们一个至关重要的启示—— [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IzQHYF9i-1631201859695)(https://www.zhihu.com/equation?tex=f(n)]) 只与 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NgIT1sEj-1631201859696)(https://www.zhihu.com/equation?tex=f(n-1)]%2Cf(n-5)%2Cf(n-11)) 相关；更确切地说：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CtM3e2yo-1631201859696)(https://www.zhihu.com/equation?tex=f(n)]%3D\min{f(n-1)%2Cf(n-5)%2Cf(n-11)}%2B1)

这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。代码如下：

我们以 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wVpbXU4l-1631201859698)(https://www.zhihu.com/equation?tex=O(n)]) 的复杂度解决了这个问题。现在回过头来，我们看看它的原理：

• [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HoZz4VQR-1631201859698)(https://www.zhihu.com/equation?tex=f(n)]) 只与[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RMAQupRc-1631201859698)(https://www.zhihu.com/equation?tex=f(n-1)]%2Cf(n-5)%2Cf(n-11))的值相关。
• 我们只关心 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d5aYrCX9-1631201859699)(https://www.zhihu.com/equation?tex=f(w)]) 的值，不关心是怎么凑出w的。

这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！

它与暴力的区别在哪里？我们的暴力枚举了“使用的硬币”，然而这属于冗余信息。我们要的是答案，根本不关心这个答案是怎么凑出来的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。**其他信息并不需要。**我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).

我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f©。我们将求解f©称作求解f(n)的“子问题”。

这就是DP（动态规划，dynamic programming）.

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

思考题：请稍微修改代码，输出我们凑出w的方案。

2. 几个简单的概念

【无后效性】

一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。

要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。

“未来与过去无关”，这就是无后效性。

（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）

【最优子结构】

回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).

f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。

大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。

引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？

能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

3. DP的典型应用：DAG最短路

问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。

​ 一张地图。边上的数字表示过路费。

这个问题能用DP解决吗？我们先试着记从S到P的最少费用为f§.
　　想要到T，要么经过C，要么经过D。从而[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gN0JDwF9-1631201859700)(https://www.zhihu.com/equation?tex=f(T)]%3D\min⁡{f©%2B20%2Cf(D)%2B10})

好像看起来可以DP。现在我们检验刚刚那两个性质：

• 无后效性：对于点P，一旦f§确定，以后就只关心f§的值，不关心怎么去的。
• 最优子结构：对于P，我们当然只关心到P的最小费用，即f§。如果我们从S走到T是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iAPnzQ4E-1631201859700)(https://www.zhihu.com/equation?tex=S+\to+P\to+Q\to+T)] ，那肯定S走到Q的最优路径是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yxxAsf5z-1631201859701)(https://www.zhihu.com/equation?tex=S\to+P\to+Q)] 。对一条最优的路径而言，从S走到**沿途上所有的点（子问题）**的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。

既然这两个性质都满足，那么本题可以DP。式子明显为：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HXzg5f7d-1631201859701)(https://www.zhihu.com/equation?tex=f§]%3D\min⁡{f®%2Bw_{R→P}})

其中R为有路通到P的所有的点， [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yn2RmPv7-1631201859702)(https://www.zhihu.com/equation?tex=w_{R→P})] 为R到P的过路费。

代码实现也很简单，拓扑排序即可。

4. 对DP原理的一点讨论

【DP的核心思想】

DP为什么会快？
　　无论是DP还是暴力，我们的算法都是在可能解空间内，寻找最优解。

来看钞票问题。暴力做法是枚举所有的可能解，这是最大的可能解空间。
　　DP是枚举有希望成为答案的解。这个空间比暴力的小得多。

也就是说：DP自带剪枝。

DP舍弃了一大堆不可能成为最优解的答案。譬如：
　　15 = 5+5+5 被考虑了。
　　15 = 5+5+1+1+1+1+1 从来没有考虑过，因为这不可能成为最优解。

从而我们可以得到DP的核心思想：尽量缩小可能解空间。

在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。

一般来说，解空间越小，寻找解就越快。这样就完成了优化。

【DP的操作过程】

一言以蔽之：大事化小，小事化了。

将一个大问题转化成几个小问题；
　　求解小问题；
　　推出大问题的解。

【如何设计DP算法】

下面介绍比较通用的设计DP算法的步骤。

首先，把我们面对的局面表示为x。这一步称为设计状态。
　　对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).
找出f(x)与哪些局面有关（记为p），写出一个式子（称为状态转移方程），通过f§来推出f(x).

【DP三连】

设计DP算法，往往可以遵循DP三连：

我是谁？ ——设计状态，表示局面
　　我从哪里来？
　　我要到哪里去？ ——设计转移

设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。这种DP也是不少的，我们以后会遇到。

总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。（这两个词是

思考题：如何把钞票问题的代码改写成“我到哪里去”的形式？
提示：求出f(x)之后，更新f(x+1),f(x+5),f(x+11).

5. 例题：最长上升子序列

扯了这么多形而上的内容，还是做一道例题吧。

最长上升子序列（LIS）问题：给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LIS）的长度。
　　e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8，长度为6。

如何设计状态（我是谁）？

我们记 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-skMhBqfJ-1631201859702)(https://www.zhihu.com/equation?tex=f(x)]) 为以 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NLeiGgKR-1631201859702)(https://www.zhihu.com/equation?tex=a_x)] 结尾的LIS长度，那么答案就是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZUihDRRZ-1631201859703)(https://www.zhihu.com/equation?tex=\max{f(x)]}) .

状态x从哪里推过来（我从哪里来）？

考虑比x小的每一个p：如果 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RDhnUsgI-1631201859703)(https://www.zhihu.com/equation?tex=a_x>a_p)] ，那么f(x)可以取f§+1.
　　解释：我们把 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kTr9oNTc-1631201859703)(https://www.zhihu.com/equation?tex=a_x)] 接在 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EhL3jLhe-1631201859704)(https://www.zhihu.com/equation?tex=a_p)] 的后面，肯定能构造一个以 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GhJrQ0vF-1631201859704)(https://www.zhihu.com/equation?tex=a_x)] 结尾的上升子序列，长度比以 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5I7a5ZpS-1631201859704)(https://www.zhihu.com/equation?tex=a_p)] 结尾的LIS大1.那么，我们可以写出状态转移方程了：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xQRs2JEG-1631201859705)(https://www.zhihu.com/equation?tex=f(x)]%3D\max_{p<x+%2C+a_p<a_x+}⁡{f§}%2B1)

至此解决问题。两层for循环，复杂度 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KDyt7Zls-1631201859706)(https://www.zhihu.com/equation?tex=O(n^2)]) .

从这三个例题中可以看出，DP是一种思想，一种“大事化小，小事化了”的思想。带着这种思想，DP将会成为我们解决问题的利器。

最后，我们一起念一遍DP三连吧——我是谁？我从哪里来？我要到哪里去？

6. 习题

如果读者有兴趣，可以试着完成下面几个习题：

一、请采取一些优化手段，以 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1d94vVKS-1631201859707)(https://www.zhihu.com/equation?tex=O(n\log+n)]) 的复杂度解决LIS问题。

提示：可以参考这篇博客 Junior Dynamic Programming–动态规划初步·各种子序列问题

二、“按顺序递推”和“记忆化搜索”是实现DP的两种方式。请查阅资料，简单描述“记忆化搜索”是什么。并采用记忆化搜索写出钞票问题的代码，然后完成P1541 乌龟棋 - 洛谷 。

三、01背包问题是一种常见的DP模型。请完成P1048 采药 - 洛谷。

下面放一篇比较好的动态规划文章：https://blog.csdn.net/WhereIsHeroFrom/article/details/120107337