二进制字符串是只包含0和1两种不同类型字符的字符串。给定一个二进制字符串和两个整数L和R。我们可以从字符串值为'0'的索引处进行大小在'L'和'R'之间的跳跃，包括'L'和'R'。我们必须从第零个索引开始，找出是否能够到达最后一个索引。

示例示例

Input1:
string str = “01001110010”
int L = 2, R = 4
Output: Yes, we can reach the last index.

Explanation

解释

我们可以从零索引跳跃三次，然后再跳跃两次到达4，这样我们就能到达最终所需的索引。

Input2:
string str = “01001110010”
int L = 2, R = 3
Output: No, we cannot reach the last index. 

Explanation

解释

我们可以进行两次跳跃，每次跳跃为2或3，如果我们从第0个索引跳跃，我们要么到达第2个索引，要么到达第3个索引，然后我们只能跳到值为'1'的索引，无法再进行进一步的跳跃。

方法一

Idea

Idea

这个想法是应用动态规划的概念。我们可以维护一个数组，表示一个位置是否可以到达。

如果我们能够达到一个位置，那么接下来的l到r个位置也可以实现。

实施

我们将创建一个函数，该函数将以字符串、左位置和右位置作为参数，并返回布尔值。

在这个函数中，我们将遍历数组，并使用嵌套的for循环遍历范围，检查当前位置减去当前范围位置是否可达，如果可达，则可以到达该位置。

最终，我们将返回DP数组的最后一个索引的状态，表示最终答案。

Example

示例

#include <bits/stdc++.h>
using namespace std;
// function to implement the DP concepts 
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results 
   
   // Initiating the first index 
   dp[0] = str[0] == '0'; 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      for(int j = l; j <= r ; j++){
         if(i-j < 0){
            break;
         }
         if(str[i-j] == '1' || dp[i-j] == 0){
            continue;
         }
         else{
            dp[i] = 1;
            break;
         }
      }
   }
   return dp[len-1];
}
int main(){
   string str = "01001110010";
   int l = 2, r = 4; 
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
   else{
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

输出

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

时间复杂度和空间复杂度

以上代码的时间复杂度为O(N^2)，其中N是给定字符串的大小。我们使用了嵌套的for循环，这使得时间复杂度为N^2。

上述代码的空间复杂度为O(N)，因为我们使用了长度为N的数组来存储DP状态。

方法二

这种方法是前一个版本的更好版本，在这种方法中，我们将维护一个整数来获取我们可以进行的跳跃次数。在每次跳跃时，如果可以跳跃，我们可以增加计数，如果在任何位置跳跃不可能，我们可以减少计数。

我们将把数据存储在DP数组的每个索引中，并稍后使用它。

Example

示例

#include <bits/stdc++.h>
using namespace std;
bool check(string str, int l, int r){
   int len = str.length(); // length of the string     
   vector<int>dp(len); // vector to store the states results     
   // initiating the first index 
   dp[0] = str[0] == '0';    
   int count = 0; // variable to maintain the count of the jump 
   
   // traversing over the array 
   for(int i=1; i<len; i++ ){
      if (i >= l) {
         count += dp[i - l];
      }
      if (i > r) {
         count -= dp[i -r- 1];
      }
      dp[i] = (count > 0) and (str[i] == '0');
   }
   return dp[len-1];
}

// main function 
int main(){
   string str = "01001110010";
   int l = 2, r = 4;  
   
   // calling the function 
   int res = check(str, l, r);    
   if(res > 0){
      cout<<"Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   } else {
      cout<<"No, we cannot reach the end of the string by starting from the zeroth index and jumping in the given range"<<endl;
   }
}

输出

Yes, we can reach the end of the string by starting from the zeroth index and jumping in the given range

时间复杂度和空间复杂度

上述代码的时间复杂度为O(N)，其中N是给定字符串的大小。我们使用单个循环遍历字符串使得时间复杂度是线性的。

上述代码的空间复杂度为O(N)，因为我们使用了长度为N的数组来存储DP状态。

结论

在本教程中，我们实现了一个代码，通过从第一个索引开始，并从给定字符串中包含'0'的索引移动给定数量的索引，来判断我们是否可以到达给定字符串的末尾。我们采用了动态规划的方法，时间复杂度为O(N^2)和O(N)，空间复杂度为O(N)。