class Solution {
public:
int cached[10001];
int dp(vector<int>& nums, int idx ) {
if(idx >= nums.size() -1) {
return 0;
}
int & ret = cached[idx];
if(ret == -1) {
ret = 1e9;
for(int j = 1; j <= nums[idx]; j++) {
ret = min(ret, dp(nums, idx + j) + 1);
}
}
return ret;
}

int jump(vector<int>& nums) {
memset(cached, -1, sizeof cached);
return dp(nums, 0);

}
};

dp