你可以使用一维数组进行计算。简单的理论,
Let F(a,b) == M(H,T)
1. F(0,b) = b
2. F(a,b) = 2^b - 1, when a+1 >= b
3. F(a,b) = F(a-1,b-1) + F(a,b-1) + 1
Let G(x,y) = F(y,x) ,then
1. G(x,0) = x // RULE (1)
2. G(x,y) = 2^x - 1, when y+1 >= x // RULE (2)
3. G(x,y) = G(x-1,y-1) + G(x-1,y) + 1 // RULE(3) --> this is useful,
// because for G(x,y) need only G(x-1,?), i.e if G - is two deminsions array, then
// for calculating G[x][?] need only previous row G[x-1][?],
// so we need only last two rows of array.
// Here some values of G(x,y)
4. G(0,y) = 2^0 - 1 = 0 from (2) rule.
5. G(1,0) = 1 from (1) rule.
6. G(1,y) = 2^1 - 1 = 1, when y > 0, from (2) rule.
G(0,0) = 0, G(0,1) = 0, G(0,2) = 0, G(0,3) = 0 ...
G(1,0) = 1, G(1,1) = 1, G(1,2) = 1, G(1,3) = 1 ...
7. G(2,0) = 2 from (1) rule
8. G(2,1) = 2^2 - 1 = 3 from (2) rule
9. G(2,y) = 2^2 - 1 = 3 when y > 0, from (2) rule.
G(2,0) = 2, G(2,1) = 3, G(2,2) = 3, G(2,3) = 3, ....
10. G(3,0) = 3 from (1) rule
11. G(3,1) = G(2,0) + G(2,1) + 1 = 2 + 3 + 1 = 6 from (3) rule
12. G(3,2) = 2^3 - 1 = 7, from (2) rule
现在,如何计算G(x,y)?
int M(int H, int T ) { return G(T,H); }
int G(int x, int y)
{
const int MAX_Y = 100;
int arr[2][MAX_Y] = {0} ;
int icurr = 0, inext = 1;
for(int xi = 0; xi < x; ++xi)
{
for( int yi = 0; yi <= y ;++yi)
{
if ( yi == 0 )
arr[inext][yi] = xi;
else if ( yi + 1 >= xi )
arr[inext][yi] = (1 << xi) - 1;
else arr[inext][yi] =
arr[icurr][yi-1] + arr[icurr][yi] + 1;
}
icurr ^= 1; inext ^= 1;
}
return arr[icurr][y];
}
// 或者一些优化
int G(int x, int y)
{
const int MAX_Y = 100;
int arr[2][MAX_Y] = {0};
int icurr = 0, inext = 1;
for(int ix = 0; ix < x; ++ix)
{
arr[inext][0] = ix;
for(int iy = 1; iy < ix - 1; ++ iy)
arr[inext][iy] = arr[icurr][iy-1] + arr[icurr][iy] + 1;
for(int iy = max(0,ix-1); iy <= y; ++iy)
arr[inext][iy] = (1 << ix ) - 1;
icurr ^= 1 ; inext ^= 1;
}
return arr[icurr][y];
}