Nhảy trò chơi V trong C++

Cho mảng arr và số nguyên d. Từ chỉ số i có thể nhảy đến i+x (1≤x≤d, i+x arr[j] và arr[i] > arr[k] với mọi k giữa i và j. Có thể bắt đầu tại bất kỳ chỉ số nào. Tìm số chỉ số tối đa có thể thăm.

Ví dụ: d=2, arr=[6,4,14,6,8,13,9,7,10,6,12], đầu ra=4. Bắt đầu tại chỉ số 10: 10→8→6→7.

Giải pháp

Sử dụng DP với memoization (top-down):

• dp[idx] = số chỉ số tối đa có thể thăm bắt đầu từ idx
• Hàm solve(arr, idx, d):
  • Nếu dp[idx] != -1: trả về dp[idx]
  • ret = 1 (chính idx)
  • Duyệt sang phải: i từ idx+1 đến min(idx+d, n-1), dừng nếu arr[i] ≥ arr[idx], cập nhật ret = max(ret, 1+solve(arr, i, d))
  • Duyệt sang trái: i từ idx-1 đến max(idx-d, 0), dừng nếu arr[i] ≥ arr[idx], cập nhật ret = max(ret, 1+solve(arr, i, d))
  • dp[idx] = ret, trả về ret
• Từ main: thử mọi chỉ số bắt đầu, lấy max

Ví dụ mã C++

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

class Solution { 
public: 
    vector<int> dp; 
    
    int solve(vector<int>& arr, int idx, int d) { 
        if (dp[idx] != -1) return dp[idx]; 
        int ret = 1; 
        int n = arr.size(); 
        
        for (int i = idx + 1; i < n; i++) { 
            if (i > idx + d) break; 
            if (arr[i] >= arr[idx]) break; 
            ret = max(ret, 1 + solve(arr, i, d)); 
        } 
        
        for (int i = idx - 1; i >= 0; i--) { 
            if (i < idx - d) break; 
            if (arr[i] >= arr[idx]) break; 
            ret = max(ret, 1 + solve(arr, i, d)); 
        } 
        
        return dp[idx] = ret; 
    } 
    
    int maxJumps(vector<int>& arr, int d) { 
        int n = arr.size(); 
        dp = vector<int>(n, -1); 
        int ret = 1; 
        for (int i = 0; i < n; i++) 
            ret = max(ret, solve(arr, i, d)); 
        return ret; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {6,4,14,6,8,13,9,7,10,6,12}; 
    cout << (ob.maxJumps(v, 2)); 
    return 0; 
}

Đầu vào

{6,4,14,6,8,13,9,7,10,6,12}, 2

Đầu ra

4