递归，动态规划，分治，分支限界，回溯之间的关系

1.递归

a.递归算法 一般用于解决三类问题

1.数据的定义是按递归定义的。例如：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

2.问题解法按[递归算法]实现。
爬楼梯：可以最终将结果递推为F[n]=F[n-1]+F[n-2];

3.数据的结构形式是按递归定义的。
a.二叉树的前中后序遍历，b.链表的遍历

b.递归方法的实现

1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理

void method(int x1,...int xn){
        if(退出条件) return;
        ....
        method(x1,....xn);
}

2.动态规划

a.思想：

1.动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，往往从所有子问题的最优解得到父问题的解
是一种以空间换时间的思维
一般情况下是自底向上进行计算，例如:LeetCode 最小路径和
a.如果使用递归算法，不进行记录那么会超出时间限制。路径图如下。

image.png

static int result ;
    public int minPathSum(int[][] grid) {
        result =Integer.MAX_VALUE;
        findPath(grid,0,0,0);
        return result;
    }

    private void findPath(int[][] grid, int indexX, int indexY,int temp) {
        temp+=grid[indexX][indexY];
        if(indexX == grid.length-1 && indexY == grid[0].length-1){
            if(result>temp){
                result = temp;
            }
        }else{
            if(indexX+1 < grid.length){
                findPath(grid,indexX+1,indexY,temp);  //向下
            }
            if(indexY+1< grid[0].length){
                findPath(grid,indexX,indexY+1,temp);  //向右
            }
        }
    }

我们应该谨慎使用递归算法，因为它们的简洁算法可能会掩盖其低效率的事实

b.如果使用动态规划（自底向上，也就是说先算n小的，然后再根据小的n算出大的n）

问题的关键：1.是否可以把原问题转化为子问题，2.子问题的性质是否和原问题一致，3.是否可以从子问题的解集合中找出原问题的最优解，也就是我们的算法会记录一些中间结果，这样再次运算时就不用重复计算。

例如：我向右走一步

image.png

其实问题就变成了子问题+1：

那么可以归纳一下逻辑：

子问题：当往右移动时是f(m,n-1),当往下移动时f(m-1,n)所以可以递归为：

public int minPathSum(int[][] grid) {
        int[][] f=new int[grid.length][grid[0].length];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(i==0&&j==0)f[i][j]=grid[i][j];
                else if(i-1<0)f[i][j]=f[i][j-1]+grid[i][j];
                else if(j-1<0)f[i][j]=f[i-1][j]+grid[i][j];
                else f[i][j]=Math.min(f[i-1][j],f[i][j-1])+grid[i][j];  //从子问题中找出该问题的最优解。
            }
        }
        return f[grid.length-1][grid[0].length-1];
    }

可以看出动态规划需要子问题和原问题产生依赖关系，从而从子问题的解求出原问题。

3.分治

a.思想

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在计算机科学中，分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）等等。

分治不会去记录子问题的中间求解结果，和动态规划一致，都需要原问题和子问题有相同的性质，再去调用自身方法解决小量级的子问题，当子问题解决后整体问题也就解决完成。
也就是说不用去递推公式来解决原问题，只要解决了所有子问题原问题就解决了
例如：快速排序
第一步：

以3为基准，进行左右排序得到
第二步：

这样，下一次做的时候就不会再去关注整个数组，只会关心前半部分

和后半部分：

采用分治法解决的问题一般具有的特征如下：

1. 问题的规模缩小到一定的规模就可以较容易地解决。
2. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。
3. 合并问题分解出的子问题的解可以得到问题的解。
4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。
   注：引用自百度百科

分治和动态规划的关系：

1. 分治法与动态规划相同:
   都要求子问题和原问题有相同的性质，只是量级不同。子问题都具有最优子结构，也就是在当前量级，返回的是最好的输出
2. 分治法与动态规划不同:
   ① 分治法通常利用递归法.
   ② 动态规划自底向上（几乎都是，逆向人的正常思维）利用迭代法求解,自顶向下（很少用，但是符合人的正常思维）利用递归法.
   ③ 分治法将分解后的子问题相互独立. 动态规划分解后的子问题为相互间有联系，而且需要从这些子问题中归纳出原问题的解.

4.分支限界和回溯法

//TODO