LeetCode——45. 跳跃游戏 II

标签：个点 nums int 45 II min 数组 LeetCode dp

LeetCode链接

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i] 
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

 思路

动态规划步骤

1.确定数组的含义和数组存储的值 这里我们要求的是跳到n-1处所需的最小次数，那么dp数组的含义就是所有能够调到一个点的路径，dp[i]的含义是调到第i个点所需的最小次数，这样返回时，只需返回dp[n-1]即可
2.确定状态转移方程 如果要调到第i个点，那么从第一个点开始，到第i-1个点都是有可能调到第i个点的 拿样例来说， [2,3,1,1,4] 如果要跳到i=3处，那么可以从i=1处跳，也可以从i=2处跳，则dp[3] = min(dp[1]+1,dp[2]+1),所以我们需要从0到i-1遍历一遍，判断某个点是否能够调到i点 由此可以确定处状态转移方程， dp[i] = min(dp[i],dp[j]+1)
3.初始化 在i=0处，不需要跳，所以dp[0] = 0,另外还需要将数组其他的项初始化为无穷大 C++代码

代码

class Solution {
public:

    int jump(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        memset(dp,0x3f,sizeof(dp));
        dp[0] = 0;
        for(int i = 1;i < n;i++){
            for(int j = 0;j < i;j++){
                if (nums[j] + j >= i)
                {
                    dp[i] = min(dp[i],dp[j]+1); 
                }
            }
        }
        return dp[n-1];
    }
};

 

标签：个点,nums,int,45,II,min,数组,LeetCode,dp
From： https://www.cnblogs.com/polang19/p/17253633.html