程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode (23) Jump Game （動態規劃）

LeetCode (23) Jump Game （動態規劃）

編輯：關於C++

題目描述

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.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

對上面的數據，使用示意圖幫助理解：
JumpGame

根據題目要求，數組裡的每個元素表示從該位置可以跳出的最遠距離，要求問從第一個元素（index=0）開始，能否達到數組的最後一個元素，這裡認為最後一個元素為終點。需要注意一下幾點：<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCsr91+nW0Mirsr/OqrfHuLrUqsvYo6zS8rTLsru05tTauvPNy7XEx+m/9qO7IMzixL/Sqsfztb207zxzdHJvbmc+1tW14zwvc3Ryb25nPqOssqKyu9Kq1+7W1cfzzaPU2jxzdHJvbmc+1tW14zwvc3Ryb25nPqOs0vK0y6OsyOe5+7/J0tTM+Ln9PHN0cm9uZz7W1bXjPC9zdHJvbmc+0rLKx7PJuaa1xKO7IMzixL/W0Mu1w/e1xMrHw7+49tSqy9i007jDzrvWw8TctO+1vbXE1+7Utr7gwOujrLWryrW8yr/J0tSyu0p1bXDEx8O01La1xL7gwOuhozxlbT7A/cjnyc/NvNbQtcS12tK7uPbK/dfptdrSu7j21KrL2M6qMqOs1PK007jDzrvWw7/J0tTM+NK7sr22/rrF1KrL2DO0pqOs0rK/ydLUzPgysr21vcj9usXOu9Sqy9gxtKahozwvZW0+DQo8aDIgaWQ9"使用動態規劃的解法">使用動態規劃的解法

本題可以用動態規劃的思想去做，考察每個位置能達到的最遠距離。第k個元素能達到的最遠距離，可能為：

max （k-1位置的最遠距離，此時可能沒有實際跳到k位置上） k+nums[k] （從k位置起跳的最遠距離）

遍歷數組元素的最遠距離，使用最遠距離判斷能否跳到終點，思路如下：

到達第k個元素前的最遠距離為max；若 max，則無法跳到k位置，程序返回false；否則，計算k位置處能達到的最遠距離，max_dis_at_k = max > k + num[k] ? max : k + num[k]；若 max_dis_at_k > 數組長度，則程序返回true。

程序最多只要遍歷一遍就可以得到結果，因此時間復雜度為O(n)。

代碼如下：

class Solution {
public:

    bool canJump(vector& nums) {
        if (!nums.size())
            return false;

        int max = nums[0];
        for (int i = 1; i != nums.size(); ++i)
        {
            if (i > max)
                return false;
            else if (nums[i] + i >= nums.size() - 1)
                return true;
            else if (nums[i] + i > max)
                max = nums[i] + i;
        }
        return true;
    }
};

不使用動態規劃的另類解法

在做完本題的時候我查找了一下相關資料，之前就有其他博客說明，本題為一道非常經典的動態規劃題目，可惜我還沒有系統學習過動態規劃，因此在剛開始看到本題的時候，沒有使用動態規劃的直覺，饒了好大一個彎才想到了上面的解法。

最初的想法是，既然數組中的元素均非負，則只要元素值全部為正，便一定可以達到終點。而無法達到終點的原因就是數組中的0元素，我們可以認為數組中某些位置的0元素相當於一個吸收態，元素跳到該位置就無法前進了。例如上圖中的第二個例子，因此在程序中判斷0是否為吸收態就可以判斷能否達到終點了。

吸收態的判斷方法為：若數組中0元素之前的所有元素跳過的距離均不超過0，則0為吸收態。

對於位置為i的0元素，從j=i-1元素向前遍歷，判斷 nums[j] + j > i 是否成立，
若成立則說明，程序可以順利跳過i位置的0元素，繼續遍歷尋找0元素若不成立則說明i位置的0元素為吸收態，無法達到終點，返回false。

根據這個思路，我們可以進行正向和反向遍歷，尋找吸收態。

正向遍歷：

class Solution {
public:

    bool canJump(vector& nums) {
        if (!nums.size())
            return false;

        int i = 0;
        while (i < nums.size() - 1)
        {
            if (nums[i] == 0)
            {
                int j = i - 1;
                while (i < nums.size() - 1 && !nums[i])
                    i++;
                i--;
                bool flag = false;
                while (j >= 0)
                {
                    if (nums[j] + j >= nums.size() - 1)
                        return true;
                    else if (nums[j] + j > i)
                    {
                        i = nums[j] + j;
                        flag = true;
                        break;                      
                    }                   
                    j--;
                }       
                if (!flag)
                    return false;
            }
            else
            {
                i = i + nums[i];
            }
        }

        return true;
    }
};

反向遍歷

class Solution {
public:

    bool canJump(vector& nums) {
        if (!nums.size())
            return false;
        if (nums.size() == 1)
            return true;
        int i = nums.size() - 1;

        for (int i = nums.size() - 1; i >= 0; --i)
        {
            if (nums[i] == 0)
            {
                int j = i - 1;
                bool flag = false;
                while (j >= 0)
                {
                    if ((i == nums.size()-1 && nums[j]+j ==i ) || nums[j] + j > i)
                    {
                        flag = true;
                        i = j + 1;
                        break;
                    }
                    j--;
                }
                if (!flag)
                    return false;
            }
        }
        return true;
    }
};