45_jump Game II 跳跃游戏II
问题描述
链接:https://leetcode.com/problems/jump-game-ii/description/
You are given a 0-indexed array of integers
nums
of lengthn
. You are initially positioned atnums[0]
.Each element
nums[i]
represents the maximum length of a forward jump from indexi
. In other words, if you are atnums[i]
, you can jump to anynums[i + j]
where:
0 <= j <= nums[i]
andi + j < n
Return the minimum number of jumps to reach
nums[n - 1]
. The test cases are generated such that you can reachnums[n - 1]
.
解析:
给定一个数组nums,你被放在0这个位置上,nums[i]表示你最多能跳多远,求 跳到最后一个位置需要的最少步数 (假定全部测试样例可以跳到最后一个位置)
基本思想
这是一个初级的一维动态规划问题。
假设nums数组的大小为n,则构建长度为n的数组dp,其中\(dp[i]\) 表示 从0位置跳到i位置需要的最少步数,则 \(dp[i]\) 依赖于 dp[0 ~i-1], 假设 dp[t] 在t位置可以跳跃到i位置,且 dp[t]最小,则 \(dp[i] = dp[t] + 1\)
代码
C++
int jump(vector<int>& nums) {
int size = nums.size();
if (size<=1) return 0;
if (nums[0]<=0) return 0;
vector<int> dp(size, 0); // dp[i] 表示 到达第i个位置需要的最少步数
for(int i=1;i<size;++i) {
int t = size;
for(int j=0;j<i;++j) {
if ((j+nums[j])>=i) {
t = min(dp[j]+1, t);
}
}
dp[i] = t;
}
return dp[size-1];
}
python
def jump(self, nums: List[int]) -> int:
size = len(nums)
if size <= 1: return 0
if nums[0] <= 0 : return 0
dp = [0] * size
for i in range(1, size):
t = size
for j in range(0, i):
if (nums[j]+j) >= i:
t = min(t, dp[j]+1)
dp[i] = t
return dp[size-1]
标签:jump,nums,int,45,II,dp,size
From: https://www.cnblogs.com/douniwanli/p/18188286