C/C++教程

LeetCode 45 Jump Game II 区间DP

本文主要是介绍LeetCode 45 Jump Game II 区间DP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Solution

很容易想到 \(dp[i]\) 表示以 \(i\) 结尾时的最小步数，考虑如何转移：
可以发现正向的 \(dp\) 比较容易：

\[dp[k] = \min(dp[k],dp[j]+1),\text{where } j+nums[j]\geq k \]

点击查看代码 
class Solution {
public:
    int jump(vector<int>& nums) {
        int MAX = 9999999;
        int dp[10005];
        int n = nums.size();
        for(int i=0;i<n;i++)dp[i] = MAX;
        dp[0] = 0;
        if(n==1)return 0;
        else{
            for(int i=0;i<n;i++){
                for(int ach = i+1;ach <= i+nums[i] && ach<n;ach++){
                    dp[ach] = min(dp[ach],1+dp[i]);
                }
            }
            return dp[n-1];
        }
    }
};
这篇关于LeetCode 45 Jump Game II 区间DP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航