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

本文主要是介绍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];     } };

这篇关于leetcode 45 跳跃游戏 最少次数 C/C++ 动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！