Recursion: Davis' Staircase 풀이 Java

Recursion: Davis' Staircase | HackerRank

 

Recursion and Backtracking에 DP를 살짝 얹은 문제

 

피보나치와 비슷하게 공식을 만들면 되지만, n이 커지는 경우를 생각해서 DP를 사용해야 한다.

return stepPerms(n - 1) + stepPerms(n - 2) + stepPerms(n - 3);

 

 

만약에 n=20 일 때, dp를 사용하지 않으면

step(19)+step(18)+step(17)

 

step(19) = step(18)+step(17)+step(16)

step(18) = step(17)+step(16)+step(15)

...

 

이런식으로 쭉쭉 재귀의 늪에 빠지게 되는데

 

n=19일때의 값이 어딘가에 저장되어 있으면 step(19)=map.get(19); 이런식으로 바로 가져올 수 있음.

 

class Result {
    
    /*
     * Complete the 'stepPerms' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER n as parameter.
     */
    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    
    public static int stepPerms(int n) {
        // Write your code here
        if (n < 0)
            return 0;
        else if (n == 0)
            return 1;
        
        if(map.containsKey(n))
        return map.get(n);
        
        map.put(n, stepPerms(n - 1) + stepPerms(n - 2) + stepPerms(n - 3));
        return map.get(n);
    }

}

 

이해하고 피보나치에 살짝 얹어보기

import java.util.*;

public class Solution {

    public static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public static int fibonacci(int n) {
        if(n==0)
        return 0;
        else if(n==1)
        return 1;
        
        if(map.containsKey(n))
        return map.get(n);
        
        map.put(n, fibonacci(n-1)+fibonacci(n-2));
        return map.get(n);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        System.out.println(fibonacci(n));
    }
}