[ LeetCode Problem: 45. 跳跃游戏 II ] 动态规划 C++ 解法

Problem: 45. 跳跃游戏 II

思路

C++版本动态规划解法，本打算通过贪心解决，但想来想去感觉还是走到了dp的路上，先思考了dp下标的含义：
如果按常规vector<int> dp(n, 0);将dp下标初始化为0，那么当dp下标存到达当前i需要的最小步数就有了冲突，dp就没有了意义，到达dp[i]所需的最大步数是i(题目数据保证了能到达num[n-1]),所以尝试将dp[i]=i进行初始化；
递推公式确定：
如果数组中下标i越靠前，并且num[i]越大，即向前能达到的下标cover=i+num[i]越大，则就有可能是最小步数，所以每当到达下标i时（可能好几次到达下标i）比较到达此下标所需要的步数，确定当前下标的最小步数 -> dp[cover] = min( dp[i]+1, dp[cover] )

Code

class Solution {
public:
        // dp[i] dp下标表示到达i需要的最小步数
        // 递推公式是选到达i能够的最小步数
    int jump(vector<int>& nums) {

        int cover = 0;
        int n = nums.size();
        vector<int> dp(n, 0);
        for(int i = 0; i < n; ++i)
            dp[i] = i;  // 赋dp初值
        for(int i = 0; i <= cover; ++i)
        {
            cover = max( i + nums[i], cover);   //当前能达到的最大距离
            if(cover > n - 1)   cover = n - 1;
            dp[cover] = min( dp[i]+1, dp[cover] );  //递推公式
        }
        return dp[n-1];
            
    }
};