Child Steps

A child is jumping up a staircase. Staircase have “n” steps. Kid can jump one, two, or three steps at a time. Count how many ways’ child can jump upstairs.

Example: n = 4
(1, 1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2), (2, 2), (3, 1), (1, 3) – 7 possibilities.

Top-Down approach

We will draw a tree for N = 4. Each child node will represent one possibility. Left child node is one step, center node two steps, and right node three steps. On green, we will put staircase steps left, on blue will be list of steps already done.

From start position we have N = 4, if for example we jump two steps we move to center child [2, (2)]. We put “2” into the list since we jumped two steps, and we have only two steps left to do. Now we have only two possibility, one step or two. When we decide to jump two more steps we are done, total list is (2, 2). However, if we jump only one step we will end in node [1, (2, 1)], from with we have only one more move, jump one-step end finish (2, 1, 1)

Every node start with its current “N” value and try to branch into three possibilities. Each child node start with N reduced by steps done for this branch. We stop our recursion algorithm when we reach N = 0.

private fun internalChildSteps(n: Int): Long {
    if (n == 0) return 1
    if (n < 0) return 0

    return internalChildSteps(n - 1) +
            internalChildSteps(n - 2) +
            internalChildSteps(n - 3)
}

fun childSteps(n: Int): Long =
    if (n <= 0) 0
    else internalChildSteps(n)

Our entry point is “childSteps” method. First we check if N is bigger than 0, if not then we do not want to run recursion.

Recursion has two basic checks:
– n == 0, this is a valid leaf of our tree, we return 1 valid move
– n < 0, this jump was bigger than n, so it is invalid return 0 valid moves

When n > 0 we run recursion:

    return internalChildSteps(n - 1) +
            internalChildSteps(n - 2) +
            internalChildSteps(n - 3)

We try all three possibilities: jump one, two and three steps. Each call will return, a count of all possible moves in this branch. We do not need to check if move is valid since each of our recursion call check for n<0 and if move was invalid it will return 0.
This will work since all valid leafs return 1, and all invalid moves return 0. Nodes just sum up values from their child, and return the total sum as root output.

Algorithm Complexity

The maximum height of our tree is equal to “N” since the smallest recursion steps reduce N by one each call. Each node splits into three more nodes so on i-th depth, node count is equal to 3ⁱ. This leads to :
\[
\sum_{i=0}^{n}3^{i} \Rightarrow O(3^{n})
\]

Memonization

When we look at our sample tree we can spot that we have two exact the same branches, one under (1,1) and another under (2). Those branches look exactly the same since each of them solve the same problem (N = 2).

To memonize this solution we can save the result in a hash map where key is problem N size, and value is move count.

private fun internalChildSteps(n: Int, memo: MutableMap<Int, Long> = mutableMapOf()): Long {
    if (n == 0) return 1
    if (n < 0) return 0

    if (memo.containsKey(n)) return memo[n]!!

    val result = internalChildSteps(n - 1, memo) +
            internalChildSteps(n - 2, memo) +
            internalChildSteps(n - 3, memo)

    memo[n] = result
    
    return result
}

Code requires few small changes:

• memo parameter with default empty array, this is our cache for sub problems solutions
• check to memo if we already have solution for this case, if yes we stop end return result
• if we do not have cached solution, we run algorithm like we use to, but we need to propagate memo for recursion calls, without that each call would have it own cache.
• After calculation, we store the result in memo

Bottom-up approach

This time we would work our way from bottom to top. When we look on our tree, to calculate result N we need solution for N-1, N-2, and N-3. This time we will pack it into an array of size N+1, index will be from 0 to N.

tab[i] – will hold solution for “i” size problem
tab[n] – will hold solution for N size problem, this is what we are looking for

We start by initialize four base case: N = { 0, 1, 2, 3 }, this will allow iteration from 4 to N without checking if “i-3”, “i-2”, “i-1” reach out of bound.

fun childTabSteps(n : Int) : Long {
    val array = arrayOfNulls<Long>(max(4, n + 1)) as Array<Long>

    array[0] = 0
    array[1] = 1
    array[2] = 2
    array[3] = 4

    for(i in 4 .. n) {
        array[i] = array[i - 3] + array[i - 2] + array[i - 1]
    }

    return array[n]
}

This code require “n’ size array, we can do much better.

fun childTabSteps(n : Int) : BigInteger {
    val array = arrayOfNulls<BigInteger>(4) as Array<BigInteger>

    array[0] = BigInteger.ZERO
    array[1] = BigInteger.ONE
    array[2] = BigInteger.TWO
    array[3] = BigInteger.TWO + BigInteger.TWO

    var dest = min(3, n)
    for(i in 4 .. n) {
        dest = (dest + 1) and 3
        array[dest] = array[(dest + 3) and 3] + array[(dest + 2) and 3] + array[(dest + 1) and 3]
    }

    return array[dest]
}

This code allow calculating childSteps for N = 1’000’000 in 30 second. Result number have 264’650 digits(!)

This time we create array of only 4 elements, three elements are previous values, and the fourth is result for current iteration.

First we initialize “dest” as minimum of (3, n) if n is smaller than 4 we will not execute any iteration so “dest” have to be equal to “N” to point current result. For the same reason we recalculate “dest” at the beginning of each loop. If loop finishes, “dest” will point at the latest result.
\[
(dest + x)\, and \, 3
\]

This formula is used to move to the next value counting from “dest”. This is why we add {1, 2, 3}, as a result it will move us to the first, second and third element next to dest (our previous results). Since our buffer is circular, we need to wrap the result.
“and 3″ it is equal to ” % 4″, this will result in circular indexing:
{0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3 ….. }