algorithm - How to count simple paths constrained by ±1 or ±2 steps?

Question

I have found this interesting dynamic-programming problem and want to know the approach .

We are given an array 'a' of size-'n'.

Each element of the array is either '1' or '2'.

We start at index '0' . If a[i]=1 , we can go to i+1 or i-1.

On the contrary, If a[i]=2 , we can go to i+1 or i+2 or i-1 or i-2.

We have to find the number of all possible paths .

**Main Constraint ** : - 1) We can go to a particular index in an array only once .

2) We always start at the index-'0' .

3) A path can end anytime we want :- )

Example array : --> [1,1,1,1]

Answer : - 4

1ST possible path : [0]

2ND possible path : [0,1]

3rd possible path : [0,1,2]

4th possible path : [0,1,2,3]

Another example : -

[2,2,2]

Answer:- 5

Paths : - [0],[0,1],[0,1,2] , [0,2,1] , [0,2] .

(This question is divided into-3-parts!)

Value(s) of n are in range : - 1) [1,100000]

                            2) [1,10]

                             3)[1,1000]

Answer 1

Consider used spaces.

0 1 2 3 4 5 6
      ^

In order to reach a number from the right, the cell just before it must have been used. Therefore, all the ways to end with x coming from the left cannot include numbers from the right. And all the ways to end with x coming from the right used x-1 and a set of moves to the right of x disjoint from the left side.

Let f(A, x) = l(A, x) + r(A, x), where l(A, x) represents all ways to end at x coming from the left; r(A, x), coming from the right.

To obtain l(A, x), we need:

(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)

To obtain r(A, x), we need:

(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).)

So it seems that

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)

The JavaScript code below tries a different 7-element array each time we run it. I leave memoisation and optimisation to the reader (for efficiently tabling f(_, 1), notice that 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)