Trò chơi nhảy trong Python

Giả sử chúng ta có một mảng các số nguyên không âm; ban đầu đứng tại chỉ số đầu tiên của mảng. Mỗi phần tử trong mảng đại diện cho độ dài nhảy tối đa tại vị trí đó. Chúng ta phải xác định có thể đến chỉ số cuối cùng hay không. Ví dụ, mảng [2,3,1,1,4] cho kết quả true. Nhảy 1 bước từ vị trí 0 đến 1, sau đó 3 bước từ vị trí 1 đến cuối.

Các bước thực hiện

• n := độ dài mảng A - 1.
• Với i từ n - 1 giảm xuống -1:
  • Nếu A[i] + i > n, thì n := i.
• Trả về true khi n = 0, ngược lại false.

Ví dụ minh họa

class Solution(object):
    def canJump(self, nums):
        n = len(nums) - 1
        for i in range(n-1, -1, -1):
            if nums[i] + i >= n:
                n = i
        return n == 0

ob1 = Solution()
print(ob1.canJump([2,3,1,1,4]))

Đầu vào

[2,3,1,1,4]

Đầu ra

True