UVa 10446 The Marriage Interview

本題連結
想法：
　　依照題意，將算過的答案記錄下來，在遞迴裡面如果已經算過，就直接回傳答案，避免重複計算。

	#include <cstdio>
	using namespace std;
	typedef unsigned long long int ullt;
	ullt C[61][61]={0};
	ullt trib (int n, int back)
	{
	if (n <= 1) return 1;
	if (C[n][back] != 0) return C[n][back];
	C[n][back] = 1;
	for (int i=1; i<=back; i++)
	C[n][back] += trib(n-i,back);
	return C[n][back];
	}
	int main()
	{
	int n, back, Case=1;
	while (scanf("%d%d",&n,&back)){
	if (n > 60) break;
	printf("Case %d: %llu\n",Case++,trib(n,back));
	}
	return 0;
	}

view raw [UVa] 10446 The Marriage Interview.cpp hosted with ❤ by GitHub