如何调整索引函数避免Lookup Table越界并充分利用空间

我正在完成一项大学作业，目标是设计递归算法，计算由一个或多个托盘序列搭建的塔的最大高度，要求下层托盘必须严格大于上层托盘。

我尝试用lookup table实现记忆化，以提升原本效率低下的算法性能。

输入处理代码 #

int 
main(int argc, char const *argv[])
{
    int lookup_memb = 0;

    // read number of element in two stacks
    scanf("%i %i
", &lenA, &lenB);

    // it's guaranteed for the first stack to always have more then zero elements
    stackA = (int*) malloc(lenA*sizeof(int));
    for (int i = 0; i < lenA; i ++) {
        scanf(" %i", stackA+i);
        stack_max = max(stack_max, stackA[i]);
    }

    // so far we estimate lookuptable size has to be at least lenA*stack_max;
    lookup_memb = lenA*stack_max;

    // however, second stack might be empty
    if (lenB) {
        stackB = (int*) malloc(lenB*sizeof(int));
        for (int i = 0; i < lenB; i ++) {
            scanf(" %i", stackB+i);
            stack_max = max(stack_max, stackB[i]);
        }

        // we have to override lookup_memb since we know stack B is not empty
        lookup_memb = lenA * lenB * stack_max;
        
    }

    
    lookup = (int*) calloc(lookup_memb, sizeof(int));
    printf("%i
", solve2(stackA, stackB, lenA, lenB, stack_max));

    free(lookup);
    free(stackA);
    free(stackB);

    return 0;
}

索引计算函数 #

随后在求解函数中，我使用以下函数确定表中的偏移量：

static
inline 
int
idx(int llenA, int llenB, int constraint) {
    // I use local-length A as x coordinate
    // local-length B as y coordinate
    // and constraint as z coordinate

    return  llenA // final pad to the specific column in row and plane
            + llenB * lenA // pad to the specific row in a plane
            + constraint * lenB * lenA; // pad to a sepcific plane
}

存在的问题 #

代码存在bug，似乎是数组越界访问导致的。这是预期之内的，因为算法初始调用时，查询的是A栈全长度、B栈全长度以及最大约束条件对应的解，这会导致行和列各越界1位。

我可以通过分配额外空间解决，将lenA设为lenA+1、lenB设为lenB+1、constraint设为constraint+1，但这似乎没必要，因为当lenA和lenB都为0或constraint为0时（且constraint保证大于0），直接返回0更简单高效。

这意味着当前表已经多了一行和一个平面。我想知道如何调整索引函数，使得参数到索引的映射仍然唯一，同时能充分利用现有表空间，减少额外分配。

最小可复现示例 #

我被要求提供最小可复现示例，如下所示。我之前犹豫是否加入，因为我不希望他人提供作业解决方案，以免涉及学术不端。

#include<malloc.h>
#include<stdio.h>

int* stackA = NULL;
int* stackB = NULL;
int* lookup = NULL;
int lenA = 0, lenB = 0;
int stack_max = 0;

// returns maximum of two integers
static inline int max(int a, int b); 

// maps unique set of parameters to a unique index in lookup table
static inline int idx(int llenA, int llenB, int constraint); 

// find the maximum height of a tower which can be built using a sequence of pallets
// under condition that every next level of the tower must be strictly larger then the next one
int solve1(int* stack, int llen, int constraint, int isA);

// find the maximum height of a tower which can be built using ywo sequences of pallets
// under condition that every next level of the tower must be strictly larger then the next one
int solve2(int* stackA, int* stackB, int llenA, int llenB, int constraint);

static
inline
int 
max(int a, int b) {
    return a < b ? b : a;
}

static
inline 
int
idx(int llenA, int llenB, int constraint) {
    // I use local-length A as x coordinate
    // local-length B as y coordinate
    // and constraint as z coordinate

    return  llenA // final pad to the specific column in row and plane
            + llenB * lenA // pad to the specific row in a plane
            + constraint * lenB * lenA; // pad to a sepcific plane
}

int 
solve1(int* stack, int llen, int constraint, int isA) {
    int fo,  // first-out element of the stack
        ret, // return value 
        // lookup index of return value for parameters given
        // if we have stack A remaining, we pass local-len as length of A, and pass 0 as length of B
        // if we have stack B remaining, we do the opposite 
        iself = idx(isA*llen, (!isA)*llen, constraint); 

    if (!llen) // if we have empty stack, we know the height of a tower we can build using it is 0
        return 0;

    // we first attempt to lookup the value, hoping it was already calculated
    ret = lookup[iself]; 
    if (ret) // calloc zeroes out lookup table, hence if ret is not zero it was already populated
        return ret;
    
    // if we got here, we know we have to compute the value
    fo = stack[0]; 

    // we either have the opportunity to take the pallet or we do not
    // in first case, we need to find whether it's better to use or discard the pallet
    // in second case we have no choice, we we discard the pallet
    ret = (constraint <= fo) ? solve1(stack+1, llen-1, constraint, isA) :  max(1 + solve1(stack+1, llen-1, fo, isA), solve1(stack+1, llen-1, constraint, isA));
    lookup[iself] = ret;
    return ret;
}

int 
solve2(int* stackA, int* stackB, int llenA, int llenB, int constraint) {

    int foA, // first-out element of stack A
        foB, // first-out element of stack B
        ret, // return value
        iself = idx(llenA, llenB, constraint); // lookup index of return value for parameters given
    
    if (!(llenA || llenB)) 
        return 0; // if both stacks are empty we know maximum height of a tower is zero

    // we first attempt to lookup the value, hoping that this calculation was already made
    ret = lookup[iself]; 
    if (ret) { // calloc zeroes out lookup table, hence if ret is not zero it was already populated
        return ret;
    }

    // if we got here, we must solve for value
    if (!llenA) { // if we only have stackB we simplify
        ret = solve1(stackB, llenB, constraint, 0);
        lookup[iself] = ret;
        return ret;
    }

    if (!llenB) { // likewise, if we only got stack A we simplify
        ret = solve1(stackA, llenA, constraint, 1);
        lookup[iself] = ret;
        return ret;
    }

    // if we got here, we must solve full problem   
    foA = stackA[0];
    foB = stackB[0];

    // if we decide to make choice based on stack A, we either have the opportunity to take the pallet or we do not
    // in the first case, we need to find whether it's better to take or discard the pallet
    // in the second case we have no choice, hence we just discard it
    int chooseA = foA < constraint ? max(1 + solve2(stackA+1, stackB, llenA-1, llenB, foA), solve2(stackA+1, stackB, llenA-1, llenB, constraint)) : solve2(stackA+1, stackB, llenA-1, llenB, constraint);
    
    // if we decide to make choice based on stack B, we either have the opportunity to take the pallet or we do not
    // in the first case, we need to find whether it's better to take or discard the pallet
    // in the second case we have no choice, hence we just discard it
    int chooseB = foB < constraint ? max(1 + solve2(stackA, stackB+1, llenA, llenB-1, foB), solve2(stackA, stackB+1, llenA, llenB-1, constraint)) : solve2(stackA, stackB+1, llenA, llenB-1, constraint); 
    
    // the solution for the current parameters is the maximum solution of stack A "route" and stack B "route"  
    ret = max(chooseA, chooseB);
    lookup[iself] = ret;

    return ret;
}

int 
main(int argc, char const *argv[])
{
    int lookup_memb = 0;

    // read number of element in two stacks
    scanf("%i %i
", &lenA, &lenB);

    // it's guaranteed for the first stack to always have more then zero elements
    stackA = (int*) malloc(lenA*sizeof(int));
    for (int i = 0; i < lenA; i ++) {
        scanf(" %i", stackA+i);
        stack_max = max(stack_max, stackA[i]);
    }

    // so far we estimate lookuptable size has to be at least lenA*stack_max;
    lookup_memb = lenA*stack_max;

    // however, second stack might be empty
    if (lenB) {
        stackB = (int*) malloc(lenB*sizeof(int));
        for (int i = 0; i < lenB; i ++) {
            scanf(" %i", stackB+i);
            stack_max = max(stack_max, stackB[i]);
        }

        // we have to override lookup_memb since we know stack B is not empty
        lookup_memb = lenA * lenB * stack_max;
    }
    
    lookup = (int*) calloc(lookup_memb, sizeof(int));
    printf("%i
", solve2(stackA, stackB, lenA, lenB, stack_max));

    free(lookup);
    free(stackA);
    free(stackB);

    return 0;
}

内容的提问来源于stack exchange，提问作者Nikolai Savulkin