ackermann动态规划算法.cpp

动态规划解一系列经典问题

#include "iostream.h" 

int A(int m,int n) 
{ 

	int i,*val,*ind; 
	if( m == 0 ) 
		return n+1; 
	val = new int[m+1]; 
	ind = new int[m+1]; 
	for( i=0;i<=m;i++ ) 
	{ 
		val[i] = -1; 
		ind[i] = -1; 
	} 
	val[0] = 1; 
	ind[0] = 0; 
	
	while(ind[m]<n) 
	{ 
		val[0]++; 
		ind[0]++; 
		for( i=0;i<m;i++ ) 
		{ 
			if(ind[i] == 1&&ind[i+1]<0) 
			{ 
				val[i+1] = val[0]; 
				ind[i+1] = 0; 
			} 
			if(val[i+1] == ind[i]) 
			{ 
				val[i+1] = val[0]; 
				ind[i+1]++; 
			} 
		} 
	} 
	return val[m]; 
} 

void main()
{
	int m,n;
	cout<<"输入m,n："<<endl;
	cin>>m>>n;
	cout<<A(m,n)<<endl;
}