算法 - 简书

算法

[TOC]

五大算法

递归与分治算法
动态规划
贪心算法
回溯法
分支限界

分治算法(走台阶)

==逆序分析== ,递归
==正序== ,循环
每次可以走一步或两步

递归(逆序)

递归就是f(n) = f(n-1) +f(n-2)+f(n-3)+...+ a+b+c;

递归==不关心f(n-1)==是如何实现的,只需知道==步骤的关联,结束的条件.==

即可求解.大问题转化微小问题,减少代码量,可读性好.

浪费空间.

最后一级有一种方法完成:f(1)=1
最后二级有两种方法完成:f(2)=2
最后三级有三种方法完成:==f(3)=f(2)+f(1)==
f(x+2)=f(x+1)+f(x)


//递归

public int f(n){

if(n<1){

        return 0;

    }

    if(n==1||n==2){

        return n;

    }

    return f(n-1)+f(n-2);

}

循环(正序)

运行快,空间占用少.

难以读懂.

从0到1有一种完成方法:sum[1]=1
从0到2有两种完成方法:sum[2]=2
从0到3有3种完成方法 :sum[3]=sum[2]+sum[1]


public int sum(n){

    int one=1;  //n

    int two=2; //n+1

    int three=0; //n+2

    for(int i=3;i<=n;i++){

        three=two+one;

        one=two;

        two=three;     

    }

    return sum;

}

动态规划(背包)

将大问题分解为小问题,动态规划下一个解依赖于上一个解.

01动态规划
完全动态规划
在有限空间的背包装入最大价值

01动态规划

动态规划==三要素==:

最优子结构
边界
状态转移方程

https://www.sohu.com/a/149075950_684445

完全动态规划

https://www.sohu.com/a/149075950_684445

==最优子结构==:10个人挖四个金矿或小于等于10个人挖五个金矿

[图片上传失败...(image-85a2da-1595645447315)]

image

贪心算法

局部最优解的累加,适用于全局最优解难以找到时.

https://www.jianshu.com/p/fa3232b9da1d

回溯算法

递归回溯(八皇后)

所谓递归回溯，本质上是深度优先的枚举法。

[图片上传失败...(image-eb5873-1595645447315)]