题目

一个数组nums,nums[i]表示在第i个位置上,最远可以往后跳nums[i]的位置；青蛙最开始就在第i个叶子上，给一个数组，问青蛙跳到最后一个叶子上最少需要条几次；

== 这是auto力扣公开笔试的第四题，前两道AC；第三道98%差最后一个用例没过，不提示那个用例不过，找不到；第四题乍一看不难，我一看时间剩余20分种我就慌了，我这人心态真差，还有20多分钟慌个毛线啊；然后一直心跳加速最后没写出来；结果自己冷静下来5分钟就写出来了==
哎，心态不行啊

解析

这是青蛙跳台阶的变形，只不过青蛙在位置i处跳的距离不是1和2;而是从1到nums[i];

code

#include
#includeusing namespace std;int main()
{int N;cin >> N;vector<int> nums;while(N--){int temp;cin >> temp;nums.push_back(temp);}int max_R = nums[0];vector<int> dp(nums.size(), INT_MAX);dp[0] = 0;for (int i = 0; i < nums.size(); i++){for (int j = i; j <= nums[i] + i && j<nums.size(); j++){dp[j] = min(dp[i] + 1, dp[j]);}}cout<<dp[nums.size() - 1]<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！