Download: 【微体系课】算法与数据结构高手养成课

什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。

随机化算法在内的一些算法，包含了一些随机输入。

五大常用算法

分治

贪婪

动态规划

回溯

穷举

五大基本算法之贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本要素
贪心选择
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。

然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

运用贪心策略在每一次转化时都取得了最优解。

问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。

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

动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

跳跃游戏 II
https://leetcode.com/problems/jump-game-ii/

题目
给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

[plaintext]
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:

假设你总是可以到达数组的最后一个位置。

思考过程
看到这道题，你的第一反应是怎么解决呢？

我甚至产生了要使用 DP 去解题的思路，不过后来一想也不对，这题不需要回退，而且是一道一维问题。

所以就想到了贪心算法。

那应该怎么使用贪心呢？

思路1
有一句话叫做以终为始，就是我们从后往前遍历。

找到一个可以可以达到结尾 i_n 的地方，如果有多个，就选择距离最远的那一个 i_n-1。

然后找到可以达到 i_n-1 最远的地方 i_n-2。

依次类推，找到最初的位置。

java 实现
  [java]
public int jump(int[] nums) {
    int count = 0;
    if(nums.length == 1) {
        return count;
    }
    // 最後一個位置。
    for(int i = nums.length-1; i > 0; i--) {
        // 取出当前位置的值
        // 从前往后循环都一样，因为你必须循环一遍，才能找到最大的那一个元素。
        // 最后前面的一个元素，肯定可以达到，至少为 1 步
        // 从前向后，记录肯定是最远的。
        for(int j = 0; j < i; j++) {
            // 哪一个值并不重要，重要的是距离
            int len = i - j;
            int maxLen = nums[j];
            // 可以达到
            if(maxLen >= len && len > 1) {
                i -= (len-1);
                break;
            }
        }
        // 次数递增
        count++;
    }
    return count;
}

理论上这个复杂度是比较高的，不过我的执行结果却是双 100。

[plaintext]
Runtime: 0 ms, faster than 100.00% of Java online submissions for Jump Game II.
Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Jump Game II.
为了避免错判，我跑了 2 次，结果都是超过双百。:)

最坏的场景就是全部都是 1，时间复杂度为 O(n^2)。