[JAVA] 알고리즘 : DFS- 조합수(메모이제이션)

 

메모이제이션 사용하지 않는 방법

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

class Main{
    public int DFS(int n, int r){
        if(n==r || r==0) return 1;
        else return DFS(n-1, r-1)+DFS(n-1, r);
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int r = kb.nextInt();
        System.out.println(T.DFS(n,r));
    }
}

 

 

메모이제이션 사용한 방법

import java.util.Scanner;

class Main{
    int[][] dy = new int[35][35];
    public int DFS(int n, int r){
        if(dy[n][r] > 0) return dy[n][r]; // 이미 구한 값이라면 재귀 호출 하지 않기
        if(n==r || r==0) return 1;
        else return dy[n][r] = DFS(n-1, r-1)+DFS(n-1, r);
    }
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int r = kb.nextInt();
        System.out.println(T.DFS(n,r));
    }
}