Number of combinations to the nth step taking 1, 2 or 3 steps at a time‽

Question

I am doing the following programming exercise: Number of combinations to the nth step. The statement is:

You need to get to the nth stair, the challenge is to get the number of different ways you can get to the nth stair with taking 1,2 or 3 steps at a time.

So for exmaple how many ways to get to the 3rd step. You can get there 4 was as shown here: [1,1,1] [1,2] [2,1] [3]

Write the method findCombs that finds all the different combinations of ways you can reach the nth step!

Until now, I have calculated by hand the combinations:

1 -> [1]

2 -> [1,1], [2]

3 -> [1,1,1], [1,2], [2,1], [3]

4 -> [1,1,1,1],[2,1,1][1,2,1],[1,1,2],[2,2],[3,1],[1,3]

5 -> [1,1,1,1,1],[2,1,1,1],[1,2,1,1],[1,1,2,1],[1,1,1,2],[2,2,1],[2,1,2],[1,2,2],[3,2],[2,3]

6 -> [1,1,1,1,1,1],[2,1,1,1,1],[1,2,1,1,1],[1,1,2,1,1],[1,1,1,2,1],[1,1,1,1,2],[2,2,1,1],[2,1,2,1],[2,1,1,2],[1,2,2,1],[1,1,2,2],[2,2,2],[3,2,1],[2,3,1],[1,2,3],[3,3]

If it is correct we have the following combinations for each number of steps:

1: 1; 2: 2; 3: 4; 4: 7; 5: 10; 6: 16...

So far I have written, that if the number of steps is 0 or negative, it should output -1; if steps are 1 or 2, we count 1 or 2 respectively.

public class Stairs {
    public int findCombs(int n){
      if(n <= 0) return -1;
      if(n <= 2) return n;
      return 0;
    }
}

Being the tests:

import org.junit.Assert;
import org.junit.Test;

public class mainTests {

    @Test
    public void test_n_3(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(4,stairs.findCombs(3));
    }

    @Test
    public void test_n_7(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(44,stairs.findCombs(7));
    }

    @Test
    public void test_n_25(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(2555757,stairs.findCombs(25));
    }

    @Test
    public void test_n_0(){
        Stairs stairs = new Stairs();
        Assert.assertEquals(-1,stairs.findCombs(0));
    }
}

How could we calculate the general case?

I have read:

So then, how could we calculate the number of combinations to the nth step taking 1, 2 or 3 steps at a time‽

EDIT: Following @Saurav Kumar Singh answer, I wrote the following:

public class Stairs {
    public int findCombs/**/(int n){
      if(n <= 0) return -1;
      if(n <= 2) return n;
      if(n == 3) return 4;
      return findCombs(n-1) + findCombs(n-2) + findCombs(n-3);
    }
}

And it passes the tests. However I would like to remove the hard coded base case:

if(n == 3) return 4;

I tried:

public class Stairs {
    public int findCombs(int n){
      if(n <= 0) return -1;
      if(n <= 2) return n;
      return findCombs(n-1) + findCombs(n-2) + n-3 > 0 ? findCombs(n-3) : 1;
    }
}

However it outputs -1 when we want to have the stairs for 3, 1 for 4, 2 for 5...

I also tried:

public class Stairs {
    public int findCombs(int n){
      if(n <= 0) return 1;
      if(n <= 2) return n;
      return findCombs(n-1) + findCombs(n-2) + findCombs(n-3);
    }
}

However when n is negative or 0, it outputs 1, instead of -1

How could be program the solution without the need to include: if(n == 3) return 4;‽

This can be solved using **dynamic programming** ! – Saurav Kumar Singh Dec 26 '19 at 09:24 — Saurav Kumar Singh, Dec 26 '19 at 09:24

score 0 · Accepted Answer · answered Dec 26 '19 at 09:31

Can be solved easily using Dynamic Programming.

if you have solved till Nth step then to reach N+1th step will be either of this -

Possible ways to reach Nth step + single step to N+1th step
Possible ways to reach N-1th step + double step to N+1th step
Possible ways to reach N-2th step + tripple step to N+1th step

Hence S(N+1) = S(N) + S(N-1) + S(N-2)

Number of combinations to the nth step taking 1, 2 or 3 steps at a time‽

1 Answers1