這是什麼

貪婪法，精神在於有限的條件下，每一步都採取對於當下最有利的選擇（短視近利），使狀態更接近答案。

舉現實的例子，股票漲就買、跌就賣的散戶心態，可以稱作貪婪法。

刷題：55. Jump Game

連結

題目

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 3 * 10^4
• 0 <= nums[i][j] <= 10^5

思考

有趣的地方在於，陣列從 0 開始計算，剛好可以看作是 起點。再來，陣列的 index 可以當作是到達該格需要的步數，而每一格的 index 與 可跳的數量，剛好可以看作是當下的最大步數。
整理上述內容，拿 Example 1 與 2 製作出列表：

Example 1
index:       |0|1|2|3|4|
item:        |2|3|1|1|4|
maxJump:     |2|4|3|4|8|
Jump>Index?  |T|T|T|T|T|
每格都是 T，有能力跳到最後一格

Example 2
index:       |0|1|2|3|4|
item:        |3|2|1|0|4|
maxJump:     |3|3|3|3|8|
Jump>Index?  |T|T|T|F|T|
出現 F，沒有能力跳到最後一格

解題

JS

/**
 * @param {number[]} nums
 * @return {boolean}
 */
const canJump = (nums) => {
  const n = nums.length;

  if (n === 0) {
    return false;
  } else if (n === 1) {
    return true;
  }

  let maxJump = 0;

  for (let i = 0; i < n; i++) {
    if (i > maxJump) {
      return false;
    }

    maxJump = Math.max(maxJump, i + nums[i]);
  }

  return true;
};

Java

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;

        if (n == 0) {
            return false;
        } else if (n == 1) {
            return true;
        }

        int maxJump = 0;

        for (int i = 0; i < n; i++) {
            if (i > maxJump) {
                return false;
            }

            maxJump = Math.max(maxJump, i + nums[i]);
        }

        return true;
    }
}

C

int max(int x, int y)
{
    if (x > y)
    {
        return x;
    }

    return y;
}

bool canJump(int *nums, int numsSize)
{

    if (numsSize == 0)
    {
        return false;
    }
    else if (numsSize == 1)
    {
        return true;
    }

    int maxJump = 0;

    for (int i = 0; i < numsSize; i++)
    {
        if (i > maxJump)
        {
            return false;
        }

        maxJump = max(maxJump, i + nums[i]);
    }

    return true;
}

看法

這題給我的感覺是小試身手，只要不斷比較是否大於 maxJump 即可達到答案。

結論

其實想想，貪婪法反應真實世界的情況，不少決策遵循短期可有效果的做法，不管後果如何，強勢地做下去就對了。
一想到不管後果就覺得可怕，如果放任不管，硬體資源會被用掉多少？似乎又回到本系列文最初的問題，時間與空間的取捨。套用當時的看法，永遠是情況調整，沒有最佳解，只有最適解。