항 전 oj HDOJ 2067 토끼 의 바둑판 (카트란 수)

항 전 oj HDOJ 2067 토끼 바둑판
제목:http://acm.hdu.edu.cn/showproblem.php?pid=2067
Problem Description
토끼 의 삼촌 이 밖에서 여행 을 다 녀 와 서 그녀 에 게 선물 을 가 져 왔 다. 토끼 는 기 쁘 게 자신의 방 으로 달 려 가 바둑판 을 뜯 어 보 니 토끼 는 실망 했다.하지만 며칠 지나 지 않 아 바둑판 의 재 미 있 는 점 을 발견 했다.출발점 (0, 0) 에서 종점 (n, n) 까지 가 는 가장 짧 은 경 로 는 C (2n, n) 입 니 다. 지금 토끼 는 대각선 (단 대각선 에 닿 을 수 있 는 격 점) 을 통과 하지 않 으 면 이런 경 로 는 얼마나 됩 니까?토끼 는 오랫동안 생각 하지 못 했 습 니 다. 지금 은 토끼 에 게 이 문 제 를 해결 해 달라 고 부탁 하고 싶 습 니 다. 당신 에 게 어렵 지 않 을 겁 니 다!
Input
매번 n (1 < = n < = 35) 을 입력 할 때마다 n 이 － 1 일 때 입력 을 끝 냅 니 다.
Output
모든 입력 데이터 출력 경로 수 에 대해 구체 적 인 형식 은 Sample 을 보십시오.
문제 풀이 의 사고 방향.
이 문 제 는 '카 틀 란 수' 의 사상 으로 풀 수 있다.카 틀 란 수 는 "곤충 은 가장자리 길이 가 n 인 정사각형 왼쪽 하단 A 점 에서 오른쪽 상단 B 점 까지 기어 다 니 며, 매번 수평 으로 오른쪽 또는 수직 으로 위로 기어 오 르 는 단위 1 만 있 을 뿐 대각선 을 넘 지 않 는 경로 수 를 계산한다" 는 연구 에서 나 온 것 이다.
'카트란 수' 의 구 해 과정 은 '동적 기획' 의 사고방식 으로 생각 할 수 있다.만약 에 Catalan (x, y) 이 원점 A 에서 출발 하여 점 (x, y) 까지 의 경로 수 를 나타 낸다 고 가정 하면 수평 으로 왼쪽 과 수직 으로 만 이동 할 수 있 기 때문에 (x - 1, y) 또는 (x, y - 1) 에서 (x, y) 로 만 이동 할 수 있 기 때문에 '(x, y) 까지 의 경로 수량' 은 '(x - 1, y) 까지 의 경로 수량' 과 'x, y - 1) 까지 의 경로 수량' 을 더 하면 문 제 를 '원점 A 에서 출발 하여 점 (x - 1, y) 으로 전환 시 켰 다.의 경로 수량 과 '원점 A 에서 출발 하여 점 (x, y - 1) 까지 의 경로 수량', 구체 적 인 전달 공식 은 C a t a l a n (x, y) = C a t a l a n (x - 1, y) + C a t a l a n (x, y - 1) Catalan (x, y) = Catalan (x - 1, y) + Catalan (x, y - 1) Catalan (x, y) = Catalan (x, y) = Catalan (x - 1, y) + Catalan (x - 1, y) + Catalan (x - 1, y) + Catalan (x, y - 1)

점 (x, y) 이 대각선 에 있 을 때 점 (x, y - 1) 에서 (x, y)

으로 만 이동 할 수 있다.

시점 (x, y) 의 y = 0 시 점 (x - 1, y) 에서 (x, y)

으로 만 이동 할 수 있 습 니 다.
다음은 전달 출구 를 찾 습 니 다. (x, y) = (1, 0) 시 이동 경 로 는 C a t a l a n (1, 0) = 1 Catalan (1, 0) = 1 Catalan (1, 0) = 1 Catalan (1, 0) = 1 입 니 다.
C a t a l a n (0, 0) = 1 Catalan (0, 0) = 1 Catalan (0, 0) = 1 로 이해 할 수 있 으 며, 위의 계산 법칙 에 따라 C a t a l a n (1, 0) = 1 Catalan (1, 0) = 1 Catalan (1, 0) = 1 Catalan (1, 0) = 1 로 계산 할 수 있다.
여기까지 카 틀 란 드 수 문제 분석 이 끝 났 습 니 다.
한편, 본 문제 의 특별한 점 은 '대각선 을 통과 하지 않 는 다' 는 상황 에서 수평 으로 왼쪽으로 또는 수직 으로 위로 운동 할 수 있다 는 것 이다. 정사각형 은 대각선 에 따라 대칭 적 이 고 대각선 양쪽 의 경로 수량 이 같 기 때문에 본 문제 가 요구 하 는 노선 수량 은 '카 틀 란 수' 문제 의 노선 수량의 두 배 이다.
동적 기획 구 해 이기 때문에 '시간 초과 귀속 함수' 버 전이 있 는데...

__int64 Catalan(int x, int y)
{
	if (!x && !y) {
		return 1;
	}
	else if (x == y) {
		return Catalan(x, y - 1);
	}
	else if (!y) {
		return Catalan(x - 1, y);
	}
	else {
		return Catalan(x, y - 1) + Catalan(x - 1, y);
	}
}

본인 의 C + + 솔 루 션

#include 
using namespace std;

int main()
{
	int n, i, j, count = 1;
	__int64 Catalan[36][36];
	for (i = 0; i < 36; i++) {
		for (j = 0; j <= i; j++) {
			if (!i && !j) {
				Catalan[i][j] = 1;
			}
			//  (x, y)       
			else if (i == j) {
				Catalan[i][j] = Catalan[i][j - 1];
			}
			//   (x, y) y=0 
			else if (j == 0) {
				Catalan[i][j] = Catalan[i - 1][j];
			}
			else {
				Catalan[i][j] = Catalan[i - 1][j] + Catalan[i][j - 1];
			}
		}
	}
	while (cin >> n) {
		if (n < 0) {
			break;
		}
		cout << count++ << " " << n << " " << 2 * Catalan[n][n] << endl;
	}
	return 0;
}

코드 는 HDOJ 플랫폼 을 통 해 검 사 를 실행 합 니 다. 오류 가 발견 되면 지적 과 수정 을 환영 합 니 다. 감사합니다!