LeetCode 1871 跳跃游戏 VII
🟠 中等偏上
https://leetcode.cn/problems/jump-game-vii/description/
递归
if(index>s.size()) return false
if(s[index]=='1') return false; //只能跳0
if(index==s.size()-1) return true;
//下一层调用，遍历所有可能落地位置。
for(int j = i+minJump;j<s.size()&&j<=i+maxJump;j++){
if(jump(j)) return true;
}
return false; //都没返回成功，返回false
bool jump(string s,int index,int min_jump,int max_jump){
if(index>s.size()-1){
return false;
}
if(s[index]=='1') return false;
if(index==s.size()-1){
return true;
}
for(int i = min_jump;i<=max_jump;i++){
if(jump(s,index+i,min_jump,max_jump)) return true;
}
return false;
}
动规
bool canReach(string s, int minJump, int maxJump) {
// return jump(s,0,minJump,maxJump);
vector<bool> dp(s.size(),false);
if(s[s.size()-1]=='0'){
dp[s.size()-1] = true;
}
else{
return false;
}
// for(int j = i+minJump;j<=i+maxJump&&j<s.size();j++){
// if(dp[j]==true){
// dp[i] = true;
// break;
// }
// }
}
return dp[0];
}
在内层循环中遍历所有可能位置，可以用滑窗优化。 但是边界位置要处理号。
bool canReach(string s, int minJump, int maxJump) {
// return jump(s,0,minJump,maxJump);
vector<bool> dp(s.size(),false);
if(s[s.size()-1]=='0'){
dp[s.size()-1] = true;
}
else{
return false;
}
int true_count = 0;
for(int i = s.size()-2;i>=0;i--){
if(i+minJump<=s.size()-1){
true_count+=dp[i+minJump]==true?1:0;
}
if(i+maxJump+1<=s.size()-1){
true_count-=dp[i+maxJump+1]==true?1:0;
}
dp[i] = true_count>0;
if(s[i]=='1'){
dp[i] = false;
}
// for(int j = i+minJump;j<=i+maxJump&&j<s.size();j++){
// if(dp[j]==true){
// dp[i] = true;
// break;
// }
// }
}
return dp[0];
}