title: Dynamic programming to solve the fibwords problem
body: <p><strong>Problem Statement:</strong> The Fibonacci word sequence of bit strings is defined as:
  <br />F(0) = 0, F(1) = 1 <br />
  F(n − 1) + F(n − 2) if n ≥ 2
  <br /> For example : F(2) = F(1) + F(0) = 10, F(3) = F(2) + F(1) = 101, etc.
  <br />
  Given a bit pattern p and a number n, how often does p occur in F(n)?<br />
  <strong>Input:</strong>
  The first line of each test case contains the integer n (0 ≤ n ≤ 100). The second line contains the bit
  pattern p. The pattern p is nonempty and has a length of at most 100 000 characters.<br />
  <strong>Output:</strong>
  For each test case, display its case number followed by the number of occurrences of the bit pattern p in
  F(n). Occurrences may overlap. The number of occurrences will be less than 2^63.
  <br /> <em>Sample input</em>: <br /> 6 <br /> 10 <br /> <em>Sample output:</em> <br /> Case 1: 5
  <br /> I implemented a divide and conquer algorithm to solve this problem, based on the hints that I found on the internet: <em>We can think of the process of going from F(n-1) to F(n) as a string replacement rule: every '1' becomes '10' and '0' becomes '1'</em>. Here is my code:</p>
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;string&gt;
  #include &lt;iostream&gt;
  using namespace std;
  #define LL long long int
  LL count = 0;
  string F[40];
  void find(LL n, char ch1,char ch2 ){//Find occurences of eiher &quot;11&quot; / &quot;01&quot; / &quot;10&quot; in F[n]
      LL n1 = F[n].length();
      for (int i = 0;i+1 &lt;n1;++i){
          if (F[n].at(i)==ch1&amp;&amp;F[n].at(i+1)==ch2) ++ count;   
      }
  }
  void find(char ch, LL n){
      LL n1 = F[n].length();
      for (int i = 0;i&lt;n1;++i){
          if (F[n].at(i)==ch) ++count;
      }
  }
  void solve(string p, LL n){//Recursion
      // cout &lt;&lt; p &lt;&lt; endl;
      LL n1 = p.length();
      if (n&lt;=1&amp;&amp;n1&gt;=2) return;//return if string pattern p's size is larger than F(n) 
      //When p's size is reduced to 2 or 1, it's small enough now that we can search for p directly in F(n)
      if (n1&lt;=2){
          if (n1 == 2){
              if (p==&quot;00&quot;) return;//Return since there can't be two subsequent '0' in F(n) for any n
              else find(n,p.at(0),p.at(1));
              return;
          }
          if (n1 == 1){
              if (p==&quot;1&quot;) find('1',n);
              else find('0',n);
              return;
          }
      }
      string p1, p2;//if the last character in p is 1, we can replace it with either '1' or '0'
                    //p1 stores the substring ending in '1' and p2 stores the substring ending in '0' 
      for (LL i = 0;i&lt;n1;++i){//We replace every &quot;10&quot; with 1, &quot;1&quot; with 0.
          if (p[i]=='1'){
              if (p[i+1]=='0'&amp;&amp;(i+1)!= n1){
                  if (p[i+2]=='0'&amp;&amp;(i+2)!= n1) return;//Return if there are two subsequent '0'
                  p1.append(&quot;1&quot;);//Replace &quot;10&quot; with &quot;1&quot;
                  ++i;
              }
              else {
              p1.append(&quot;0&quot;);//Replace &quot;1&quot; with &quot;0&quot;
              }
          }
          else {
              if (p[i+1]=='0'&amp;&amp;(i+1)!= n1){//Return if there are two subsequent '0'
                  return;
              }
              p1.append(&quot;1&quot;);
          }
      }
      solve(p1,n-1);
      if (p[n1-1]=='1'){
          p2 = p1;
          p2.back() = '1';
          solve(p2,n-1);
      }
  }
  main(){
      F[0] = &quot;0&quot;;F[1] = &quot;1&quot;;
      for (int i = 2;i&lt;38;++i){
          F[i].append(F[i-1]);
          F[i].append(F[i-2]);
      }//precalculate F(0) to F(37)
      LL t = 0;//NumofTestcases
      int n; string p;
      while (cin &gt;&gt; n &gt;&gt; p) {
          count = 0;
          solve(p,n);
          cout &lt;&lt; &quot;Case &quot; &lt;&lt; ++t &lt;&lt; &quot;: &quot; &lt;&lt; count &lt;&lt; endl;
      }
  }
  </code></pre>
  <p>The above program works fine, but with small inputs only. When i submitted the above program to codeforces i got an answer wrong because although i shortened the pattern string p and reduces n to n', the size of F[n'] is still very large (n'&gt;=50). How can i modify my code to make it works in this case, or is there another approach (such as dynamic programming?). Many thanks for any advice.</p>
  <ul>
  <li><br />More details about the problem can be found here: <a href="https://codeforces.com/group/Ir5CI6f3FD/contest/273369/problem/B" rel="nofollow noreferrer">https://codeforces.com/group/Ir5CI6f3FD/contest/273369/problem/B</a></li>
  </ul>