请人做外贸网站应注意什么,企业网站建设找哪家,集团高端网站,品牌网球给你一个非负整数数组 nums #xff0c;你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。
这道题用动态规划做#xff0c;时间复杂度很高 …给你一个非负整数数组 nums 你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。
这道题用动态规划做时间复杂度很高 但毕竟在学动态规划嘛那就不用贪心算法优化了。
状态转移方程 dp[ij] min(dp[ij], dp[i] 1) 边界条件 dp[0] 0
class Solution {
public:int jump(vectorint nums) {int top nums.size();int dp[100005];memset(dp, 0x3f3f3f3f, sizeof(dp));dp[0] 0;for(int i 0; i top; i){for(int j 1; j nums[i]; j){dp[ij] min(dp[ij], dp[i] 1);}}return dp[top-1];}
};
