สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่เรียกว่า arr และจำนวนเต็ม d ในขั้นตอนเดียวเราสามารถข้ามจากดัชนี i ไปยัง −
-
i + x โดยที่:i + x
-
i - x โดยที่:i - x>=0 และ x ในช่วง 1 ถึง d.
โดยที่ n คือขนาดของอาร์เรย์ นอกจากนี้ เราสามารถข้ามจากดัชนี i ไปยังดัชนี j เมื่อ arr[i]> arr[j] และ arr[i]> arr[k] สำหรับดัชนีทั้งหมด k ระหว่าง i และ j เราสามารถเลือกดัชนีของอาร์เรย์และเริ่มกระโดดได้ เราต้องหาดัชนีให้ได้มากที่สุด
ดังนั้นหากอินพุตเท่ากับ d =2 และความสูงเท่ากับ
จากนั้นผลลัพธ์จะเป็น 4 เราสามารถเริ่มต้นที่ดัชนี 10 เราสามารถกระโดดจากดัชนี 10 --> 8 --> 6 --> 7 ดังที่แสดง ดังนั้นหากเราเริ่มต้นที่ดัชนี 6 เราจะสามารถข้ามไปยังดัชนี 7 ได้เท่านั้น เราไม่สามารถข้ามไปยังดัชนี 5 เนื่องจาก 13> 9 เราไม่สามารถข้ามไปยังดัชนี 4 เนื่องจากดัชนี 5 อยู่ระหว่างดัชนี 4 และ 6 และ 13> 9 และเรา ไม่สามารถข้ามจากดัชนี 3 ไปยังดัชนี 2 หรือดัชนี 1 ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดอาร์เรย์ dp
-
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้อาร์เรย์ arr, idx, d,
-
ถ้า dp[idx] ไม่เท่ากับ -1 แล้ว −
-
ส่งคืน dp[idx]
-
-
ยกเลิก :=1
-
n :=ขนาดของ arr
-
สำหรับการเริ่มต้น i :=idx + 1 เมื่อ i
-
ถ้า i> idx + d แล้ว −
-
ออกจากวง
-
-
ถ้า arr[i]>=arr[idx] แล้ว −
-
ออกจากวง
-
-
ret :=สูงสุดของ ret และ 1 + แก้ (arr, i, d)
-
-
สำหรับการเริ่มต้น i :=idx - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -
-
ถ้าฉัน
-
ออกจากวง
-
-
ถ้า arr[i]>=arr[idx] แล้ว −
-
ออกจากวง
-
-
ret :=สูงสุดของ ret และ 1 + แก้ (arr, i, d)
-
-
dp[idx] :=ยกเลิก
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
n :=ขนาดของ arr
-
dp :=กำหนดอาร์เรย์ขนาด n และเติมด้วย -1
-
ยกเลิก :=1
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ret :=สูงสุดของ ret และแก้ปัญหา (arr, i, 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));
} อินพุต
{6,4,14,6,8,13,9,7,10,6,12}, 2 ผลลัพธ์
4
