Triple Step

8.1 Triple Step: A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

BF: Every step in the tree, we can branch out to 1 to 2 or 3 steps from our current step. The number of root to leaf paths are the total number of steps we could take.

DP: Notice the overlapping subtrees in the image below. Store these results as the total number of root to leaf paths in that subtree.

long int tripleStep(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    else if (n == 2) {
        return 2;
    }

    return tripleStep(n - 1) + tripleStep(n - 2) + tripleStep(n - 3);
}

int tripleStep(int n) {
    if (n == 1 || n == 0)
        return 1;

    else if (n == 2)
        return 2;

    int prev_sum[3] = {1,1,2};
    for (int i = 3; i <= n; i++) {
        int temp = prev_sum[2];
        int temp2 = prev_sum[1];
        prev_sum[2] = prev_sum[0] + prev_sum[1] + prev_sum[2];
        prev_sum[1] = temp;
        prev_sum[0] = temp2;
    }

    return prev_sum[2];
}

Python BF and DP Memiozation:

def three_step_stairs_bf(steps):
    def __three_step_stairs_bf(steps, cur):
        if cur == steps:
            return 1
        elif cur > steps:
            return 0
        else:
            return __three_step_stairs_bf(steps, cur + 1) + \
                   __three_step_stairs_bf(steps, cur + 2) + \
                   __three_step_stairs_bf(steps, cur + 3)
    return __three_step_stairs_bf(steps, 0)


def three_step_stairs_dp(steps):
    memory = {}
    def __three_step_stairs_dp(steps, cur):
        if cur in memory:
            return memory[cur]
        elif cur == steps:
            return 1
        elif cur > steps:
            return 0
        else:
            count_1 = __three_step_stairs_dp(steps, cur + 1)
            count_2 = __three_step_stairs_dp(steps, cur + 2)
            count_3 = __three_step_stairs_dp(steps, cur + 3)
            memory[cur] = count_1 + count_2 + count_3
            return memory[cur]
    return __three_step_stairs_dp(steps, 0)


for steps in range(0, 10):
    print(steps, three_step_stairs_bf(steps))


for steps in range(0, 1000):
    print(steps, three_step_stairs_dp(steps))