考虑使用的空间。
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 = falselet arr = []let n = 7for (let i=0; i<n; i++) arr[i] = Math.ceil(Math.random() * 2)console.log(JSON.stringify(arr))console.log('')let res = 0for (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)
