55. Jump Game

1.問題

• 給予一個非負整數的array, 每個值表示可達的最大長度, 判斷是否能達到最後一個index

2.想法

• 提問

• function header, parameter

• test input

• 說明想法

  • 動態規劃, 由於需要判斷到最後時的剩餘步數是否>=0

  • 因此dp內所要儲存的值為到此格所剩餘的步數, 由於一開始就在0了, 因此dp[0] = 0, 之後的位置所剩下的步數為前一個所剩餘的步數 -1, 所以dp[1] = max(dp[0], num[0]) - 1;

  • 如果有dp為負數則回傳false

  • 最後判斷dp[last]是否為0

• 測試計算複雜度

  • O(N)

3.程式碼

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> remain(nums.size(), 0);
        remain[0] = 0;
        for (int i = 1; i < nums.size(); i++) {
            remain[i] = max(remain[i - 1], nums[i - 1]) - 1;
            if (remain[i] < 0) {
                return false;
            }
        }
        return true;
    }
};