class Solution { public: int d[10001]; int N; int go(vector<int>& nums,int now) { if(now>=N-1) return 0; if(d[now]!=0x7f7f7f7f) return d[now]; d[now] = 0x7ffff; int now1 = 0x7ffff; for(int i = nums[now];i>=0;i--) { if(i+now>N) i = N-now; now1 = min(now1,go(nums,i+now)+1); } d[now] = now1; return d[now]; } int jump(vector<int>& nums) { fill(d,d+10001,0x7f7f7f7f); N = nums.size(); return go(nums,0); } };
탑 다운 연습