algorithm - 如何计算受 ±1 或 ±2 步限制的简单路径？

Question

我发现了这个有趣的动态规划问题，想知道它的方法。

我们得到一个大小为“n”的数组“a”。

数组的每个元素要么是“1”，要么是“2”。

我们从索引 '0' 开始。如果 a[i]=1 ，我们可以转到 i+1 或 i-1。

相反，如果 a[i]=2 ，我们可以转到 i+1 或 i+2 或 i-1 或 i-2。

我们必须找到所有可能路径的数量。

**主要约束**:- 1) 我们只能访问数组中的特定索引一次。

2) 我们总是从索引“0”开始。

3) 路径可以在我们想要的任何时候结束:-)

示例数组:--> [1,1,1,1]

答案:- 4

第一个可能的路径:[0]

2ND 可能路径:[0,1]

第三条可能路径:[0,1,2]

第四条可能路径:[0,1,2,3]

另一个例子:-

[2,2,2]

答案:- 5

路径:- [0]、[0,1]、[0,1,2]、[0,2,1]、[0,2]。

(本题分为三部分!)

n 的值在范围内:- 1) [1,100000]

                            2) [1,10]

                             3)[1,1000]

Answer 1

考虑使用过的空间。

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)