用动态规划法计算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)?