[백준 1010] 다리 놓기

분류 

dp

요구사항

다리를 놓을 수 있는 경우의 수 구하기

풀이

n<=m 이니깐 m개 중에서 n개를 고르면 자동적으로 겹치지 않고 놓을 수 있는 경우가 된다

이는 nCr의 조합으로 풀 수 있다

nCr = n-1Cr-1 + n-1Cr 의 점화식으로 풀이 가능하다

 

#include <iostream>
#include <string.h>
using namespace std;
int d[40][40];
int n, m;
int func(int r, int c) {
	if (r == c) return 1;
	if (r == 0) return 0;
	if (c == 0) return 1;
	if (c < 0) return 0;
	if (r < 0) return 0;

	int &ref = d[r][c];
	if (ref != -1) {
		return ref;
	}

	return ref = func(r - 1, c - 1) + func(r - 1, c);


}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		scanf("%d%d", &n, &m);
		memset(d, -1, sizeof(d));
		printf("%d\n", func(m, n));

	}
}