leetcode1306.跳跃游戏

• 跳跃游戏
  -这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

• 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

• 注意，不管是什么情况下，你都无法跳到数组之外。

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 动态规划？

/Welcome to GDB Online.GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JSCode, Compile, Run and Debug online from anywhere in world.*/
#include <stdio.h>
#include<vector>
#include<memory>
#include<iostream>
using namespace std;
class Solution{
public:bool isreach = false;int ti = 1;//target_indexvoid dfs(int start,vector<int>& visit,vector<int>& arr){if(isreach){//找到结果return;}if(visit[start]==1){//访问循环return;}if(start == ti){isreach = true;}else{visit[start] = 1;if(start+arr[start]<arr.size()){dfs(start+arr[start],visit,arr); }if(start-arr[start]>-1){dfs(start-arr[start],visit,arr);  }visit[start] = 0;// 清楚当前路径的标记}}bool canReach(std::vector<int>& arr,int start){//正向：从5开始，进行2^n次方查找，设置是否访问标志for(int i=0;i<arr.size();i++){if(arr[i]==0){ti = i;cout<<"target index is "<<ti<<endl;break;}}vector<int> visit(arr.size());dfs(start,visit,arr);return isreach;}
};int main()
{// vector<int> arr = {4,2,3,0,3,1,2};// int start = 5;vector<int> arr = {3,0,2,1,2};int start = 2;unique_ptr<Solution> mysolo = unique_ptr<Solution>(new Solution());bool res = mysolo->canReach(arr,start);cout<<res<<endl;return 0;
}

• 修改一处即可

class Solution{
public:bool isreach = false;int ti = 1;//target_indexvoid dfs(int start,vector<int>& visit,vector<int>& arr){if(isreach){//找到结果return;}if(visit[start]==1){//访问循环return;}if(arr[start] == 0){isreach = true;}else{visit[start] = 1;if(start+arr[start]<arr.size()){dfs(start+arr[start],visit,arr); }if(start-arr[start]>-1){dfs(start-arr[start],visit,arr);  }visit[start] = 0;// 清楚当前路径的标记}}bool canReach(std::vector<int>& arr,int start){//正向：从5开始，进行2^n次方查找，设置是否访问标志vector<int> visit(arr.size());dfs(start,visit,arr);return isreach;}
};