[数据结构与算法]LeetCode: 45. 跳跃游戏 II（DP算法）

题目：LeetCode: 45. 跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        if (len == 1) {
            return 0;
        }
        
        vector<int> counts(len, len);
        counts[len - 1] = 0;
        for (int i = len - 2; i >= 0; --i) {
            tag(nums, counts, i);
        }
        return counts[0];
    }

private:
    

    void tag(vector<int>& nums, vector<int>& counts, int i) {
        int len = nums.size();
        int maxJump = nums[i];
        for (int step = 1; step <= maxJump; ++step) {
            if (i + step > len - 1) {
                break;
            }
            int tmpCnt = counts[i + step] + 1;
            counts[i] = (tmpCnt > counts[i]) ?  counts[i] : tmpCnt;
        }
    }
};