조합의경우수 메모이제이션

경우의 수, nCr는 (n-1Cr-1)+ (n-1Cr) 와 같다는 공식을 사용한다.

n은 요소의 개수, r은 그 중 몇 개 선택할지

 

그리고 n==r 인 경우 경우의 수는 1, 요소가 3개에 3개를 선택한다면 경우의 수는 1개 뿐

r==0 인 경우도 경우의 수는 1이다, 요소가 아무리 많아도 0개를 선택할 경우의 수는 1개 뿐

 

6C4는 15의 경우의 수가 나온다.

코드

class 조합의경우수$메모이제이션{
	static int[][] dy=new int[35][35];
	static int cnt1,cnt2;
	
	static int DFS1(int n, int r){
		cnt1++;
		if(n==r || r==0) return 1;
		else return DFS1(n-1, r-1)+DFS1(n-1, r);
	}
	
	static int DFS2(int n, int r){
		cnt2++;
		if(dy[n][r]!=0) return dy[n][r]; //이미 계산해놓은게 있다.
		if(n==r||r==0) return 1;
		else {
			return dy[n][r]=DFS2(n-1,r-1)+DFS2(n-1,r);
		}
		
	}
	
	public static void main(String[] args){
		int n=6;
		int r=4;
		
		System.out.print("메모이제이션 사용 안함 ");
		System.out.println(DFS1(n, r)+" "+cnt1);
		System.out.print("메모이제이션 사용 함 ");
		System.out.println(DFS2(n, r)+" "+cnt2);
	}
}

---

결과

메모이제이션 사용 안함 15 29
메모이제이션 사용 함 15 17

---

숫자가 적어서 메모이제이션 효과가 미미해보이지만 아래처럼 조금만 증가해도 기하급수적으로 반복호출하게 된다.

메모이제이션 사용 안함 30045015 60090029
메모이제이션 사용 함 30045015 401