Nhảy ếch (Frog Jump) trong C++

Éch bắt đầu ở đáy đầu tiên (vị trí 0), muốn nhảy đến đáy cuối. Các đáy ở vị trí tăng dần. Nhảy đầu tiên phải là 1 đơn vị. Nếu nhảy trước là k, nhảy tiếp theo phải là k-1, k, hoặc k+1. Chỉ nhảy về phía trước.

Ví dụ

stones = [0,1,3,5,6,8,12,17] → true

Lộ trình: 0→1 (k=1), 1→3 (k=2), 3→5 (k=2), 5→8 (k=3), 8→12 (k=4), 12→17 (k=5).

Thuật toán: DFS + Memoization

Trạng thái: (pos, k) — vị trí đáy hiện tại và độ dài nhảy vừa rồi.

• Dùng unordered_map<long long, int> visited lưu kết quả đã tính.
• Key = pos | (k << 11) (giả sử pos, k < 2048).
• Từ pos, thử tất cả đáy pos:
  • gap = stones[i] - stones[pos].
  • Nếu gap < k-1: bỏ qua (nhảy quá ngắn).
  • Nếu gap > k+1: dừng (các đáy sau xa hơn nữa).
  • Nếu k-1 ≤ gap ≤ k+1: đệ quy canCross(i, gap).
• Trường hợp cơ sở: pos == n-1 → trả về true.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    unordered_map<lli, int> visited;

    bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
        lli key = pos | (k << 11);
        if (visited.find(key) != visited.end()) return visited[key];
        for (int i = pos + 1; i < stones.size(); i++) {
            int gap = stones[i] - stones[pos];
            if (gap < k - 1) continue;
            if (gap > k + 1) return visited[key] = false;
            if (canCross(stones, i, gap)) return visited[key] = true;
        }
        return visited[key] = (pos == stones.size() - 1);
    }
};

int main() {
    Solution ob;
    vector<int> v = {0, 1, 3, 5, 6, 8, 12, 17};
    cout << ob.canCross(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n^2) — mỗi trạng thái (pos, k) tính tối đa 1 lần, số trạng thái ≤ n * maxJump.
• Không gian: O(n^2) cho memoization.

Input / Output

Input:  0,1,3,5,6,8,12,17
Output: 1 (true)