算法探究

算法之途广而宽

Created: January 17, 2022 12:58 AM

Read Me

算法很难搞懂，但想下心底要努力的目标，其实一切都可以忍受的

• 基础常用算法

  • 查找算法

    🔢 非树查找算法

    • 二分查找

    • 差值查找算法

    • 斐波那契查找算法

    🌲 树查找

    • 二叉树查找

    • 平衡二叉树

    • 红黑树查找

    • B树查找

  • 排序算法

    • 冒泡排序

    • 选择排序

    • 插入排序算法

    • 快速排序

    • 归并排序算法

    • 计数排序

    • 基数排序

    • 堆排序

• 动态规划

  • 基本概念

    动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，而我们希望找到具有最优值的解。动态规划算法与分治法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

    动态规划问题经分解得到的子问题往往不是互相独立的。需要保存已解决的子问题的答案，而在需要时再找出已保存的答案，这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

    动态规划有两个重要的概念：

    • 状态：解决某一问题的中间结果，它是子问题的一个抽象定义。
    • 状态转移方程：状态与状态之间的递推关系。

    动态规划解题步骤：

    1. 状态定义：找出子问题抽象定义。
    2. 确定状态转移方程：找出状态与状态之间的递推关系。
    3. 初始状态和边界情况：最简单的子问题的结果，也是程序的出口条件 。
    4. 返回值：对于简单问题，返回值可能就是最终状态；对于复杂问题可能还需对最终状态做一些额外处理。

  • 示例题目一

    题目描述：假设正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？其中 n 是一个正整数。

    示例 1：

    输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    1. 1 阶 + 1 阶
    2. 2 阶
    复制代码

    示例 2：

    输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶
    复制代码

    这道题有两个关键特征：

    • 要求给出达成某个目的的解法个数；
    • 不要求给出每一种解法对应的具体路径。

    这样的问题往往可以用动态规划进行求解。对于这个问题，每次爬楼梯只有两种情况：

    • 最后一步爬 1 级台阶，前面有 n - 1 级台阶，这种情况下共有f(n - 1)种方法；
    • 最后一步爬 2 级台阶，前面有 n - 2 级台阶，这种情况下共有f(n - 2)种方法；

    f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，这就是本题用到的递推关系。下面就根据动态规划的四个步骤来看那一下：

    1. 状态定义：初始化一个f数组，f[i]表示爬到i级台阶的方法数量；
    2. 状态转移方程：f(n)=f(n-1)+f(n-2)；
    3. 初始状态：一级台阶时，共1种爬法；两级台阶时，可以一级一级爬，也可以一次爬两级，共有2种爬法。即f[1] = 1，f[2] = 2；
    4. 返回值：f[n] ，即 n 级台阶共有多少种爬法。

    动态规划实现代码如下：

    /**
    * @param {number} n
    * @return {number}
    */
    const climbStairs = function(n) {
        // 初始化状态数组
        const f = [];
        // 初始化已知值
        f[1] = 1;
        f[2] = 2;
        // 动态更新每一层楼梯对应的结果
        for(let i = 3;i <= n;i++){
            f[i] = f[i-2] + f[i-1];
        }
        // 返回目标值
        return f[n];
    };

  • 分析使用场景

    上面用动态规划的思想解决了爬楼梯的问题，当然我们的目的并不是为了解决这个问题，而是通过这个问题来看动态规划，下面就来重新认识一下动态规划。

    上面说过了分支问题，它的核心思想是：把一个问题分解为相互独立的子问题，逐个解决子问题后，再组合子问题的答案，就得到了问题的最终解。

    动态规划的思想和“分治”有点相似。不同之处在于，“分治”思想中，各个子问题之间是独立的：比如说归并排序中，子数组之间的排序并不互相影响。而动态规划划分出的子问题，往往是相互依赖、相互影响的。

    那什么样的题应该用动态规划来做？要抓以下关键特征：

    • 最优子结构，它指的是问题的最优解包含着子问题的最优解——不管前面的决策如何，此后的状态必须是基于当前状态（由上次决策产生）的最优决策。就这道题来说，f(n)和f(n-1)、f(n-2)之间的关系（状态转移方程）印证了这一点。
    • 重叠子问题，在递归的过程中，出现了反复计算的情况。
    • 无后效性，无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

    所以，只要需要解决的问题符合这三个关键特征，就可以使用动态规划来求解。