คำอธิบายโจทย์
มีอาร์เรย์ arr และระยะกระโดดสูงสุด d กระโดดจาก i ไป j ได้ก็ต่อเมื่อ: |i-j|≤d, arr[i]>arr[j], และ arr[i]>arr[k] สำหรับ k ระหว่าง i,j เริ่มจาก index ใดก็ได้ หาจำนวน index สูงสุดที่เยี่ยมชมได้
ตัวอย่าง
arr = [6,4,14,6,8,13,9,7,10,6,12], d=2 → Output: 4
เส้นทาง: 10→8→6→7 (index 10→8→6→7)
วิธีแก้ปัญหา
ใช้ DP + Memoization (Top-down):
- dp[idx] = จำนวน index สูงสุดที่เยี่ยมชมได้เริ่มจาก idx
- ลองกระโดดซ้ายและขวาในระยะ d หยุดเมื่อเจอค่า ≥ arr[idx]
- dp[idx] = 1 + max(dp[next]) สำหรับ next ที่ถูกต้อง
- ลองเริ่มจากทุก index หาค่าสูงสุด
การทำงานของโค้ด
#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 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.assign(n, -1);
int ret = 1;
for(int i=0; i
อินพุต
{6,4,14,6,8,13,9,7,10,6,12}, 2
เอาต์พุต
4
