[DynamicProgramming] HackerRank Algorithms in Java ‘Davis’ Staircase’ solution

Problem

Davis has a number of staircases in his house and he likes to climb each staircase 1,2, or 3 steps at a time. Being a very precocious child, he wonders how many ways there are to reach the top of the staircase. Given the respective heights for each of the s staircases in his house, find and print the number of ways he can climb each staircase, module 10^9 + 7 on a new line. For example, there is s = 1 staircase in the house that is n = 5 steps high. Davis can step on the following sequences of steps:

1 1 1 1 1
1 1 1 2
1 1 2 1 
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2

Solution

Recursion으로 분류되어 있지만 동적 계획법으로 풀어야 한다. 왜냐하면 재귀로 풀면 시간초과가 나기 때문이다!!! (도대체 그럼 왜…) 잘 보면 규칙이 보이고 식을 세워 구하면 된다. 참고로, 문제에 분명 10000000007 값을 mod 하라고 하지만 작성하는 순간 int의 범위를 넘는다며 에러가 난다… 문제 무엇..

Code

// Complete the stepPerms function below.
    static int stepPerms(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1; 
        if(n >= 3) dp[3] = 4;
        if(n >= 2) dp[2] = 2; 
        
        for(int i = 4; i <= n; i++) dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

        return dp[n];
    }