Greedy Algorithm

貪婪演算法（Greedy Algorithm）是一種在每個決策階段都採取當前狀態下最好或最佳（局部最優）的選擇，希望最後拼湊出全體最佳（全局最優）結果的策略。

它最大的特點是直觀、簡單且執行速度快，但並不保證所有問題都能找到絕對的全體最佳解，對範圍相當廣泛的許多問題它能產生整體最優解或者是整體最優解的近似解。

核心概念

• 局部最優：每一個步驟都只看眼前最有利的選擇。
• 絕不回頭：做出的決策不會被重新考慮或改變。
• 性質需求：通常需要問題本身具備「最佳子結構」與「貪婪選擇性質」才能得到正確答案。

範例

直接以 Leetcode 題目作為範例說明。

題目：在陣列的第一格，每一格的數字代表你最多可以往後跳幾步，問能不能到達最後一格

Example 1:
Input: nums = [2,3,1,1,4]
Output: true

Example 2:
Input: nums = [3,2,1,0,4]
Output: false

var canJump = function(nums) {
    const n = nums.length
    let farIdx = 0      // 記錄最遠可以到哪一個 index

    for (let i = 0; i < n; i++) {
        if (farIdx < i) return false            // 檢查最遠可到的 index 可否到當下這裡
        farIdx = Math.max(farIdx, i + nums[i])  // 貪婪的重點：每次只取最遠可以到哪
    }

    return farIdx >= n - 1
};