Số Nhảy Tối Thiểu Để Đến Cuối Mảng (Minimum Number of Jumps)

Giới thiệu

Cho mảng số nguyên dương, mỗi phần tử cho biết số bước nhảy tối đa từ vị trí đó. Từ chỉ số 0, tìm số nhảy nhỏ nhất để đến chỉ số cuối cùng.

Đầu vào và Đầu ra

Đầu vào: {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Đầu ra: 3 (0->1 (giá trị 3), nhảy 3 bước đến chỉ số 4 (giá trị 9), nhảy 9 bước đến cuối).

Thuật toán Quy hoạch động

Mảng jumps[i] lưu số nhảy tối thiểu từ 0 đến i. Khởi tạo jumps[0]=0, các phần tử còn lại = ∞. Với mỗi i, kiểm tra các j < i nếu j + arr[j] ≥ i thì cập nhật jumps[i] = min(jumps[i], jumps[j]+1).

minPossibleJump(list, n)
Begin
    định nghĩa jumps[n]
    if n=0 or list[0]=0 return ∞
    jumps[0] := 0
    for i := 1 to n-1 do
        jumps[i] := ∞
        for j := 0 to i-1 do
            if i <= j + list[j] and jumps[j] != ∞ then
                jumps[i] := min(jumps[i], jumps[j] + 1)
                break
            done
        done
    done
    return jumps[n-1]
End

Ví dụ C++

#include <iostream>
using namespace std;

int min(int x, int y) { return (x < y) ? x : y; }

int minPossibleJump(int list[], int n) {
    int *jumps = new int[n];
    if (n == 0 || list[0] == 0) return INT_MAX;
    jumps[0] = 0;
    for (int i = 1; i < n; i++) {
        jumps[i] = INT_MAX;
        for (int j = 0; j < i; j++) {
            if (i <= j + list[j] && jumps[j] != INT_MAX) {
                jumps[i] = min(jumps[i], jumps[j] + 1);
                break;
            }
        }
    }
    return jumps[n-1];
}

int main() {
    int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    int size = 11;
    cout << "Số nhảy tối thiểu để đến cuối: " << minPossibleJump(list, size);
    return 0;
}

Kết quả

Số nhảy tối thiểu để đến cuối: 3