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