Demo: Hopping Chaos II

Let's continue with the same problem, now using the "Bottom-Up" or iterative approach.

Problem Description

// A puppy named Chaos is eager to reach a bowl of
// treats at the top of a series of n stacks of
// crates. Each stack is higher by 1 crate than
// the previous one, forming a structure similar
// to stairs. Each time, Chaos can hop either 1
// stack or 2 stacks upward in his excitement. In
// how many distinct ways can Chaos reach the bowl?

// Write a function `hoppingChaos` that, given a
// number n as the input, determines the number
// of distinct ways Chaos can reach the bowl.

// The minimum amount of stacks is 1 and the maximum is 50.

// Example 1:

// Input: 2
// Output: 2

// Chaos can reach the top of the stack in two distinct ways:

// 1. Hop 1 stack, then hop 1 more stack.
// 2. Hop 2 stacks in one go.

// Example 2:

// Input: 4
// Output: 5

// Chaos can reach the top of the stack in five distinct ways:

// 1. Hop 1 stack, hop 1 stack, hop 1 stack, then hop 1 stack.
// 2. Hop 1 stack, hop 1 stack, then hop 2 stacks in one go.
// 3. Hop 1 stack, then hop 2 stacks in one go, then hop 1 stack.
// 4. Hop 2 stacks in one go, hop 1 stack, then hop 1 stack.
// 5. Hop 2 stacks in one go, then hop 2 stacks in one go again.

function hoppingChaos(n) {
  // implementation
}


console.log(hoppingChaos(2) === 2);
console.log(hoppingChaos(3) === 3);
console.log(hoppingChaos(4) === 5);
console.log(hoppingChaos(8) === 34);
console.log(hoppingChaos(13) === 377);
console.log(hoppingChaos(17) === 2584);
console.log(hoppingChaos(21) === 17711);
console.log(hoppingChaos(50) === 20365011074);
// All test cases should log true.

Bottom-Up Walkthrough

The bottom-up approach is an iterative method where we solve the problem by building up solutions from the smallest subproblems to the larger ones. In this approach, we use an additional data structure, usually an array but hashmap is fine as well, often called dp, which stands for dynamic programming.

Algorithm

Let's start building our solution from the ground up.

1. Initialize the dp array: Create an array dp of size n + 1 to store the number of ways to reach each stack. We are using n + 1 since arrays are 0-index based.

2. Fill the array with initial values: These values are the solutions for the simplest cases, or in this problem, the solutions when we have one or two stacks. These are our base cases from the recursive solution:

3. dp[1] = 1: There is only one way to reach the first stack (a single hop).

4. dp[2] = 2: There are two ways to reach the second stack (two single hops or one two-stack hop).

5. Iterate through all Values from 3 to n: For each stack number from 3 to n, compute the number of ways to reach that stack using the sum of the ways to reach the previous stack and the stack before that, for example, dp[3] = dp[2] + dp[1]

6. This is why it is necessary to first fill in the initial values; let's see what would happen without them if we started iterating from 1. dp[1] = dp[0] + dp[-1], and since dp[-1] is undefined we would get NaN as a result.

7. Return the Final Result: At the end of the process, dp[n] contains the number of distinct ways to get to stack n and we should return that number.

---

Let's do a step-by-step walkthrough where we have 5 stacks. We will use a different color for each path.

• Step 1: In the first step, we initialize a dp array and fill it with 6 values, as arrays are 0-index based.

• Step 2: We fill the array with the base case values. There is one unique path to the first stack and two unique paths to the second stack.

• Step 3: In the third step, we start iterating through the rest of the stacks and filling them one by one by summing values from the previous two stacks. In the first iteration, for the third stack, the result is 3.

• Step 4: In the fourth step, we calculate the number of distinct ways to get to the fourth stack by summing the results for stacks 3 and 2, which equals 5.

• Step 5: Finally, for the fifth stack, we do the same. The number of distinct ways to get there is the number of ways to get to stack 4 plus the number of ways to get to stack 3, which is5 + 3 and equals 8. This is the result that we return.

---

Solution

Let's see the code implementation:

function hoppingChaos(n) {
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  dp[2] = 2;

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

Time and Space Complexity

The time complexity for the iterative solution is the same as with the recursive one with memoization which is O(N).

Since our dp array stores the results for every subproblem, and there are n subproblems, the total amount of space required is, also, O(N).

We've already hinted that in this problem we don't need to use an array or a hashmap as we can solve it simply by using an additional temp variable. This will reduce the Space Complexity to O(1).

Let's see the code implementation:

function hoppingChaos(n) {
  if (n === 1) {
    return 1;
  }
  if (n === 2) {
    return 2;
  }

  let prev2 = 1;
  let prev1 = 2;

  for (let i = 3; i <= n; i++) {
    const temp = prev1 + prev2;
    prev2 = prev1;
    prev1 = temp;
  }

  return prev1;
}

With that being said, please note that in more complex problems, this space optimization might not be possible. This is why we've shown you an example with the dp being an array.

In the next assignment, we'll discuss different choices for the data structure in DP problems.