C++: Số nhảy tối thiểu con ếch về nhà

Bài toán: Chuỗi nhị phân S độ dài n, '1'=có sen, '0'=không. Ếch bắt đầu vị trí 1 (index 0), muốn đến n (index n-1). Nhảy phải ≤ d, chỉ nhảy lên '1'. Tìm số nhảy tối thiểu.

Thuật toán tham lam: Luôn nhảy xa nhất có thể (tối đa d) đến vị trí có '1'. Nếu không nhảy được → -1.

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(string s, int d) {
    int n = s.size();
    int pos = 0, jumps = 0;
    while (pos < n - 1) {
        int next = -1;
        for (int i = min(pos + d, n - 1); i > pos; i--) {
            if (s[i] == '1') { next = i; break; }
        }
        if (next == -1) return -1;
        pos = next;
        jumps++;
    }
    return jumps;
}

int main() {
    cout << solve("10010101", 4) << endl; // 2 (0→3→7)
    return 0;
}

Kết quả

2

Vị trí 0-based: 0→3 (nhảy 3), 3→7 (nhảy 4).