title: CYK algorithm top down design with memoization
body: <p>I run the CYK algorithm, however, I am trying to do it as a top down design (memoization), any help?</p>
  
  <pre><code>bool canDerive(nonterminal S, string w) {
      return canDeriveRec(S, w, 0, w.size());
  }
  
  /* Can you derive the substring [start, end) of w from S? */
  bool canDeriveRec(nonterminal S, string w, int start, int end) {
      /* Base case: Single characters */
      if (end - start == 1) {
          return whether there is a production S -&gt; a, where a = w[start];
      }
  
      /* Recursive case: Try all possible splits */
      for (each production S -&gt; AB) {
          for (int mid = start + 1; mid &lt; end; mid++) {
              if (canDeriveRec(A, w, start, mid) &amp;&amp;
                  canDeriveRec(B, w, mid, end)) {
                  return true;
              }
          }
      }
      return false;
  }
  </code></pre>