Chương trình tìm số nhảy tối thiểu để đến cuối mảng bằng Python

Cho mảng nums các số dương. Bắt đầu tại chỉ số 0, mỗi phần tử cho biết độ nhảy tối đa tại vị trí đó. Tìm số nhảy ít nhất để đến chỉ số cuối n-1.

Ví dụ: [3, 4, 3, 0, 1] → 2 (nhảy 0→1→4).

Quy trình giải quyết (Greedy)

1. Khởi tạo end = 0, jumps = 0, farthest = 0.
2. Với i từ 0 đến len(nums)-1:
   • Cập nhật farthest = max(farthest, nums[i] + i).
   • Nếu i == end và i != len(nums)-1: tăng jumps, gán end = farthest.
3. Trả về jumps.

Ví dụ mã nguồn

class Solution:
    def jump(self, nums):
        end = 0
        jumps = 0
        farthest = 0
        for i in range(len(nums)):
            farthest = max(farthest, nums[i] + i)
            if i == end and i != len(nums) - 1:
                jumps += 1
                end = farthest
        return jumps

ob = Solution()
print(ob.jump([3, 4, 3, 0, 1]))  # Output: 2

Đầu vào

[3, 4, 3, 0, 1]

Đầu ra

2