Recursive stair climbing algorithm

Question

I am trying to change the following algorithm from recursive to iterative, and am having problems doing so. (Book: "Cracking the Coding Interview.")

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

Book's answer (recursive):

public static int countWays(int n, int[] map) {

    if (n < 0)
        return 0;
    if (n == 0)
        return 1;
    if (map[n] > -1)
        return map[n];

    map[n] = countWays(n - 1, map) + countWays(n - 2, map) + countWays(n - 3, map);

    return map[n];

}

My answer (iterative):

public static int countWays(int n, int[] map) {

    for (int i = 1; i <= n; i++) {

        //Problem with writing it this way: index could be negative
        map[i] = map[i - 1] + map[i - 2] + map[i - 3];

    }

    return map[n];

}

One problem I am having with my given answer is that the line "map[i - 1] + map[i - 2] + map[i - 3]" could result in negative indices, which would throw an error.

There may be other problems with my code.

Could someone please help in writing this?

For iterative O(n) and O(log(n)) solutions in Python, see [this answer](https://stackoverflow.com/a/40920969/832230). — Asclepius, Dec 05 '16 at 20:09

ronn164 · Answer 1 · 2016-03-17T05:06:36.880

The iterative approach you are using is called bottom-up dynamic programming. It is different from top-down recursion with memoization. Bottom-up is more efficient because you are avoiding the stack overhead associated with recursion.

Steps:
1 -> 1 = 1 way
2 -> 11, 2 = 2 ways
3 -> 111, 12, 21, 3 = 4 ways
4 -> 1111, 112, 121, 211, 22, 31, 31 = 7 ways

Another way to get around your index problem is to create an array with a minimal size of 3 and start from the 3rd index. You're using a little more space but it simplifies your code.

public int countWaysDP(int n) {
    if (n < 0) {
        throw new IllegalArgumentException();
    }
    int[] dp = new int[Math.max(3, n)];
    dp[0] = 1; // 1
    dp[1] = 2; // 11, 2
    dp[2] = 4; // 111, 12, 21, 3
    for (int i = 3; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];    
    }
    return dp[n - 1];
}

Hope this helps your training.

Adam Evans · Accepted Answer · 2015-07-22T03:34:56.817

1

Hardcode the first index to have a value of 1, then put each term of the sum in its own if statement to check for a negative index. If the index is negative, don't include it in the sum.

Alternatively, you could just hardcode the first three values, then start at 4 and not worry about it.

edited Jul 22 '15 at 03:34

answered Jul 22 '15 at 03:27

Adam Evans

2,072
1
20
29

score 1 · Answer 3 · answered Jul 22 '15 at 08:54

public static int countWays(int n, int[] map) {

   if(n == 0 || n==1)
     return 1;
   if(n == 2)
     return 2;
   map[0] = 1;
   map[1] = 1;
   map[2] = 2;
   for (int i = 3; i <= n; i++) {

       //Problem with writing it this way: index could be negative
       map[i] = map[i - 1] + map[i - 2] + map[i - 3];

   }

return map[n];

}

score 0 · Answer 4 · answered Jul 22 '15 at 03:49

Since this is clearly a coding interview question... I'm going to show you a similar solution to review, In Scala, to help you learn the fundamentals.

import scala.annotation.tailrec

object Main {

/**
 * Count ways to make change...
 */
 def countChange(money: Int, coins: List[Int]): Int = {
    def reduce(money: Int, coins: List[Int]): Int ={
      if (money == 0) 1
      else if (money < 0 || coins.isEmpty) 0
      else reduce(money - coins.head, coins) + reduce(money, coins.tail)
    }
    reduce(money, coins)
  }
}

Recursive stair climbing algorithm

4 Answers4