考虑使用的空间。

0 1 2 3 4 5 6
      ^

为了从右边获得一个数字，必须使用它之前的单元格。因此，所有以x左边结尾的方式都不能包含右边的数字。而所有方法的最终结果x都来自使用x-1的右侧，以及x从左侧向右侧不相交的一组移动。

设f(A, x) = l(A, x) + r(A, x)，其中l(A, x)表示从左侧开始以x结尾的所有方式；r(A, x)，来自右边。

要获取l(A, x)，我们需要：

(1) all ways to reach (x-1)
    = l(A, x-1)

  (there are no numbers used to
   the right of x, and since
   x is used last, we could not
   have reached x-1 from the right.)

(2) all ways to reach (x-2):
    cleary we need l(A, x-2). Now
    to reach (x-2) from the right,
    the only valid path would have
    been ...(x-3)->(x-1)->(x-2)
    which equals the number of ways
    to reach (x-3) from the left.

    = l(A, x-2) + l(A, x-3)

要获取r(A, x)，我们需要：

(1) all ways to reach (x+1) so as
    to directly go from there to x
    = l(A, x-1)

  (We can only reach (x+1) from (x-1).)

(2) all ways to reach (x+2) after
    starting at (x+1)
    = l(A, x-1) * f(A[x+1...], 1)

  (To get to the starting point in
   A[x+1...], we must first get to
   (x-1).)

所以看来

f(A, x) = l(A, x) + r(A, x)

  l(A, x) =
    l(A, x-1) + l(A, x-2) + l(A, x-3)

  r(A, x) =
    l(A, x-1) + l(A, x-1) * f(A[x+1...], 1)

每次我们运行以下JavaScript代码时，它都会尝试使用不同的7元素数组。我将备忘录和优化留给读者（为了有效地制表f(_, 1)，请注意l(_, 1) = 1）。

function f(A, x){

  if (x < 0 || x > A.length - 1)

    return 0



  return l(A, x) + r(A, x)



  function l(A, x){

    if (x < 0 || x > A.length - 1)

      return 0

    if (x == 0)

      return 1



    let result = l(A, x-1)



    if (A[x-2] && A[x-2] == 2){

      result += l(A, x-2)



      if (A[x-3] && A[x-3] == 2)

        result += l(A, x-3)

    }



    return result

  }



  function r(A, x){

    if (x < 0 || x >= A.length - 1 || !(A[x-1] && A[x-1] == 2))

      return 0



    let result = l(A, x-1)



    if (A[x+2] && A[x+2] == 2)

      result += l(A, x-1) * f(A.slice(x+1), 1)



    return result

  }

}





function validate(A){

  let n = A.length



  function g(i, s){

    if (debug)

      console.log(s)

    let result = 1

    let [a, b] = [i+1, i-1]



    if (a < n && !s.includes(a))

      result += g(a, s.slice().concat(a))

    if (b >= 0 && !s.includes(b))

      result += g(b, s.slice().concat(b))



    if (A[i] == 2){

      [a, b] = [i+2, i-2]



      if (a < n && !s.includes(a))

        result += g(a, s.slice().concat(a))

      if (b >= 0 && !s.includes(b))

        result += g(b, s.slice().concat(b))

    }



    return result

  }



  return g(0, [0])

}



let debug = false



let arr = []

let n = 7

for (let i=0; i<n; i++)

  arr[i] = Math.ceil(Math.random() * 2)

console.log(JSON.stringify(arr))

console.log('')



let res = 0

for (let x=0; x<arr.length; x++){

  let c = f(arr,  x)

  if (debug)

    console.log([x, c])

  res += c

}



if (debug)

  console.log('')

let v = validate(arr)

if (debug)

  console.log('')

console.log(v)

console.log(res)