[게임 & 다이내믹 플랜] poj2068Nim

기억화된 검색은 데이터 규모가 비교적 작은 상황에서 비교적 쓰기 좋다.
이 바둑의 문제는 동태적인 기획을 빌려 해답을 구할 수 있고 형식적으로는 귀속이며 실질적으로는 하나의 수조를 빌려 중복된 계산을 피할 수 있다.
코드는 다음과 같습니다.

#include<iostream>
using namespace std;
int search(int count,int leftNumber);
int n,maxNumber[50];
int dp[25][10001];
int main(){
	int total;
	while(cin>>n&&n){
		cin>>total;
		n=n*2;
		for(int i=0;i<n;i++)
			cin>>maxNumber[i];
		for(int i=0;i<n;i++)
		for(int j=0;j<=total;j++)
			dp[i][j]=-1;	//the process of initialization
		search(0,total);
		cout<<dp[0][total]<<endl;
	}
	//system("pause");
	return 0;
}

int search(int count,int leftNumber){
	if(dp[count][leftNumber]!=-1)
		return dp[count][leftNumber];
	//boundary conditions
	if(leftNumber==0){
		dp[count][leftNumber]=1;
		return 1;
	}
	else if(leftNumber==1){
		dp[count][leftNumber]=0;
		return 0;
	}
	for(int i=1;i<=maxNumber[count];i++){
		if((leftNumber-i)>=0&&search((count+1)%n,leftNumber-i)==0){
			dp[count][leftNumber]=1;
			return 1;
		}
	}
	dp[count][leftNumber]=0;
	return 0;
}