Leetcode 45

题目要求

给定一个n个整数的序列nums(0-indexed)，每个位置表示你一次移动的最大距离。求从0开始移动到n-1位置上所需要的移动次数。

核心算法和原理

• 一般想法是线性DP，判断到达每个位置所需要的最小移动次数。显然算法复杂度为O(n^2)。

• 更优的线性DP算法：构建一个新的序列s，s[i]表示从0-i位置一步所能到达的最远位置。

• Sub problem: s[i] = max(s[i-1], s[i] + i)（我能到达i必然能到达i-1，所以子结构可满足）。

• 细节：直接从头把nums数组改成s数组即可，省一点空间。

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        int size = nums.size();
        for(int i = 1; i < size; i++){
            nums[i] = max(nums[i - 1], nums[i] + i);    
//modify nums[i] -> maximum distance we can reach in one step from index i
        }
        int ans = 0;
        for(int i = 0; i < size - 1; i = nums[i]){
            ans++;
        }

        return ans;
    }
};