跳跃游戏 II
跳跃游戏 II
思路：
想到用队列，一层一层往外扩。
相当于暴力了，还是过了，因为稍微剪了一点枝。
代码：
class Solution {
public:int jump(vector<int>& nums) {int n=nums.size();queue<int> q;//<下标>unordered_map<int,int> m;//键值对：键：下标 值：最小次数q.push(0);m[0]=0;while(!q.empty()){auto t=q.front();q.pop();int zuiyuanjuli=t+nums[t];for (int i = t + 1; i <= zuiyuanjuli && i < n; i++) {// 如果没有访问过或者找到了更少的跳跃次数if (m.find(i) == m.end() || m[t] + 1 < m[i]) {m[i] = m[t] + 1;q.push(i); // 将新位置加入队列// 如果已经到达终点if (i == n - 1){return m[i];}}}}return m[n-1];}
};动态规划：
dp[i]:表示到达i所需的最短次数。
const int N = 1e4+10;
int dp[N];
class Solution {
public:int jump(vector<int>& nums) {memset(dp,0x3f,sizeof dp);dp[0]=0;for(int i=0;i<nums.size();i++){int step=nums[i];for(int j=i+1;j<=i+step&&j<nums.size();j++){dp[j]=min(dp[j],dp[i]+1);}}return dp[nums.size()-1];}
};贪心：
觉得代码不咋好理解，好难啊。。。