leetcode 45 跳跃游戏 最少次数 C/C++ 动态规划

动态转移方程   dp[pos] = min{dp[pos-k] +1}   当a[pos-k] >= k ,  k 是两次状态之间a的物理距离。    动态规划并不是这个例子的最好解法，时间复杂度 n^2, 空间复杂度有n, 在 n 比较大时，在有些平台并不能通过。
class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size());  //dp[i]   到达第i个位置，最少跳跃次数  
        return min(nums,dp,nums.size()-1);
    }
    int min(vector<int> &nums, vector<int> &dp, int pos){
        if(dp[pos]) return dp[pos];
        if(pos == 0) return 0;
        int min_num = pos + 1;
        for(int k = 1; k <= pos; k++){
            if(nums[pos-k] >= k){                    //上一个位置的数的值大于或者等于 两个位置之间的距离时，可以尝试跳一次，记录下它的情况。
                int temp = min(nums,dp,pos-k);
                min_num = min_num > (temp + 1) ? (temp+1) :min_num;  // 求不同解之间的最优解。
            }
        }
        dp[pos] = min_num !=pos + 1? min_num : 0;
        return dp[pos];
    }
};