用动态规划法计算Ackerman函数A(m,n)的值，Ackerman函数定义如下：
A(m,n)=n+1(m=0);A(m,n)=A(m-1,1),(m>0,n=0);A(m,n)=A(m-1,A(m,n-1)),(m>0,n>0)
要求算法只占用O(m)的空间，用两个数组val[0:m]和ind[0:m]，使得对任何i有val[i]=A(i,ind[i])，目前有2种算法，第一，可以发现函数有如下规律：当m=0时，A(0,n)=n+1;当m=1时，A(1,0)=A(0,1)=2,A(1,n)=A(0,A(1,n-1))=A(1,n-1)+1=n+2;当m=2时A(2,0)=A(1,1)=3,A(2,n)=A(1,A(2,n-1))=A(2,n-1)+2=3+2n;……由此可列出算法如下：
#include<iostream>
#define N 10
using namespace std;
int ack[N][N]={0};
int ackerman(int m, int n)
{
for(int i=0; i<N; i++)
ack[0][i] = i+1;
for(int j=1; j<N; j++)
{
ack[j][0] = ack[j-1][1];
for(int k=1; k<N; k++)
ack[j][k] = ack[j-1][ack[j][k-1]];
}
return ack[m][n];
}
int main()
{
for(int i=0;i<4;i++)
cout<<i<<" "<<ackerman(2,i)<<endl;
return 1;
}
但是这个算法的不足在于，它实际需要的空间并不是O(m),例如，如果需要计算A(1,1)的值，按代码执行，A(1,1)=A(0，2)，因此，若要求出最终结果，在计算a[0][i]的过程中，必须迭代到i=2,因此，它所需的空间也就超过O(m)了。此外，实际需要的空间在计算之前也无法预计。
第二种算法：
define M 100
# include <stdio.h>
# include <string.h>
int result[M];
int index[M];
Int ackerman (int m, int n)
{
Int value, temp;
if (result[m] > 0 && index[m] == n)
return result[m];
if (m == 0)
{
index[m] = n;
result[m] = n + 1;
return result[m];
}
else if (m > 0 && n == 0)
{
value = ackerman (m - 1, 1);
result[m - 1] = value;
index[m - 1] = 1;
return result[m - 1];
}
else
{
value = ackerman (m, n - 1);
result[m] = value;
index[m] = n - 1;
temp = value;
value = ackerman (m - 1, (int)value);
result[m - 1] = value;
index[m - 1] = temp;
return result[m - 1];
}
}
main ()
{
int n, m;
while (scanf ("%d%d", &n, &m) != -1)
{
if (n == 0 && m == 0)
break;
memset (result, 0, sizeof (result));
printf ("%I64d\n", ackerman (n, m));
}
}
此算法的问题在于，这个算法中出现了递归，但是参考一般动态规划的例程，均未有递归的出现。
问题1：究竟题目要求中两个规模为m的数组应该怎样与第一个算法相结合？
问题2：第二个算法可否称其为动态规划，其空间复杂度是否确实为O(m)?
