Jump Game V trong C ++

Giả sử chúng ta có một mảng các số nguyên gọi là arr và một số nguyên d. Trong một bước, chúng ta có thể chuyển từ chỉ mục i đến -

i + x trong đó:i + x
i - x trong đó:i - x> =0 và x trong phạm vi từ 1 đến d.

Ở đây n là kích thước của mảng. Ngoài ra, chúng ta chỉ có thể nhảy từ chỉ số i sang chỉ số j khi arr [i]> arr [j] và arr [i]> arr [k] cho tất cả các chỉ số k giữa i và j. Chúng ta có thể chọn bất kỳ chỉ mục nào của mảng và bắt đầu nhảy. Chúng tôi phải tìm số lượng chỉ số tối đa mà chúng tôi có thể truy cập.

Vì vậy, nếu đầu vào giống như d =2 và chiều cao giống như

thì đầu ra sẽ là 4, chúng ta có thể bắt đầu ở chỉ số 10. chúng ta có thể nhảy từ chỉ số 10 -> 8 -> 6 -> 7 như hình. Vì vậy, nếu chúng ta bắt đầu từ chỉ số 6, chúng ta chỉ có thể nhảy đến chỉ mục 7. Chúng ta không thể chuyển sang chỉ mục 5 vì 13> 9. Chúng ta không thể chuyển đến chỉ mục 4 vì chỉ số 5 nằm giữa chỉ mục 4 và 6 và 13> 9. Và chúng tôi cũng không thể nhảy từ chỉ mục 3 sang chỉ mục 2 hoặc chỉ mục 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một mảng dp
Xác định một hàm giải quyết (), điều này sẽ nhận một mảng arr, idx, d,
nếu dp [idx] không bằng -1, thì -
- trả về dp [idx]
ret:=1
n:=kích thước của arr
để khởi tạo i:=idx + 1, khi tôi
- nếu tôi> idx + d, thì -
  - Ra khỏi vòng lặp
- nếu arr [i]> =arr [idx], thì -
  - Ra khỏi vòng lặp
- ret:=tối đa ret và 1 + giải (arr, i, d)
để khởi tạo i:=idx - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -
- nếu tôi
  - Ra khỏi vòng lặp
- nếu arr [i]> =arr [idx], thì -
  - Ra khỏi vòng lặp
- ret:=tối đa ret và 1 + giải (arr, i, d)
dp [idx]:=ret
trả lại ret
Từ phương thức chính, thực hiện như sau -
n:=kích thước của arr
dp:=Xác định một mảng có kích thước n và điền vào giá trị này bằng -1
ret:=1
để khởi tạo i:=0, khi i
- ret:=tối đa ret và giải quyết (arr, i, d)
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
   cout << (ob.maxJumps(v, 2));
}

Đầu vào

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

Jump Game V trong C ++

Ví dụ

Đầu vào

Đầu ra