<p>First of all, we do know that finding any longest common subsequence of two sequences with length n cannot be done in O(n<sup>2-ε</sup>) time unless the Strong Exponential Time Hypothesis fails, see:
<a href="https://arxiv.org/abs/1412.0348" rel="nofollow noreferrer">https://arxiv.org/abs/1412.0348</a></p>

<p>This pretty much implies that you cannot count the number of ways how to align common subsequences to the input sequences in O(n<sup>2-ε</sup>) time.
On the other hand, it is possible to count the number of ways of such alignments in O(n<sup>2</sup>) time. It is also possible to count them in O(n<sup>2</sup>/log(n)) time with the so-called four-Russians speed-up.</p>

<p>Now the real question if you really intended to calculate this or you want to find the number of <em>different</em> subsequences? I am afraid that this latter is a #P-complete counting problem. At least, we do know that counting the number of sequences with a given length that a regular grammar can generate is #P-complete:</p>

<blockquote>
  <p>S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting
  and random generation of strings in regular languages.
  In ACM-SIAM Symposium on Discrete Algorithms
  (SODA), pages 551–557, 1995</p>
</blockquote>

<p>This is a similar problem in that sense that counting the number of <em>ways</em> a regular grammar can generate sequences of a given length is a trivial dynamic programming algorithm. However, if you do not want to distinguish generations resulting the same sequence, then the problem turns from easy to extremely hard. My natural conjecture is that this should be the case for sequence alignment problems, too (longest common subsequence, edit distance, shortest common superstring, etc.).</p>

<p>So if you would like to calculate the number of <em>different</em> subsequences of two sequences, then very likely your current algorithm is wrong and any algorithm cannot calculate it in polynomial time unless P = NP (and more...).</p>
How to calculate the number of longest common subsequences
<p>I'm trying to calculate the <strong>amount</strong> of longest possible subsequences that exist between two strings. </p>

<p>e.g.
  String X = "efgefg";
  String Y = "efegf";</p>

<p>output: The Number of longest common sequences is: 3 
  (i.e.: efeg, efef, efgf - this doesn't need to be calculated by the algorithm, just shown here for demonstration)</p>

<p>I've managed to do this in O(|X|*|Y|) using dynamic programming based on the general idea here: <a href="https://stackoverflow.com/questions/2207987/cheapest-path-algorithm">Cheapest path algorithm</a>. </p>

<p>Can anyone think of a way to do this calculation with better runtime efficiently?</p>

<p>--Edited in response to Jason's comment.</p>