C语言超大矩阵定义失败，malloc实现过慢的解决方案求助

尝试定义大小为MAX（2000000000）的二维memo矩阵时，编译报错：

error: size ‘16000000016000000004’ of array ‘memo’ exceeds maximum object size ‘9223372036854775807’
10 | int memo[MAX + 1][MAX + 1];
| ^~~~

已知这是内存超限问题，但尝试用malloc动态分配二维数组时效率极低：

int **memo = (int **)malloc((MAX + 1) * sizeof(int *));
for (int i = 0; i <= MAX; i++) {
    memo[i] = (int *)malloc((MAX + 1) * sizeof(int));
}

同时需要每次扫描新输入时将矩阵值重置为-1，完整代码如下：

#include <stdio.h>
#include <stdlib.h>

#define MAX 2000000000 //必须是2000000000

unsigned int n1,n2,f1,f2;
int i,j;
char next_char;

int memo[MAX + 1][MAX + 1];

void scan_fast(int* int_input){
    *int_input=0;
    next_char=0;
    while( next_char < '0' || next_char > '9' ) // 跳过非数字字符
        next_char = getchar();
    while( next_char >= '0' && next_char <= '9' )
    {
        (*int_input) = ((*int_input)<<1) + ((*int_input)<<3) + next_char - '0';
        next_char = getchar();
    }
}

int comida(int f1, int f2) {
    /* 终止条件 */
    if (f1 == 0 && f2 == 0){ return 1; }

    if (memo[f1][f2] != -1) {
        return memo[f1][f2];
    }

    printf("f1: %d, f2: %d\n", f1, f2);
    
    if (f1 >= n1 && f2 >= n2 && comida(f1 - n1, f2 - n2)) {
        memo[f1][f2] = 1;
        return 1;
    } else if (f1 >= n2 && f2 >= n1 && comida(f1 - n2, f2 - n1)){
        memo[f1][f2] = 1;
        return 1;
    } else {
        /* 当前路径无解 */
        memo[f1][f2] = 0;
        return 0;
    }
    
}

int main() {
    scanf("%d %d %d %d", &f1, &f2, &n1, &n2);

    while(!(f1 == 0 && f2 == 0 && n1 == 0 && n2 == 0)) {
        /* 重置矩阵 */
        for (i = 1; i <= MAX; i++) {
            for (j = 1; j <= MAX; j++) {
                memo[i][j] = -1;
            }
        }

        if (comida(f1,f2)) printf("SI\n");
        else printf("NO\n");

        scan_fast(&f1); scan_fast(&f2); scan_fast(&n1); scan_fast(&n2);
    }
    return 0;
}

首先明确核心问题：MAX=2e9的二维数组完全不可能存储——按每个int占4字节计算，总大小约为1.6e19字节（16EB），远超任何计算机的内存甚至存储容量，因此必须放弃预分配大数组的思路，改用以下方案：

1. 数学推导（最优方案） #

观察递归逻辑，问题本质是判断是否存在非负整数a,b，使得：

f1 = a*n1 + b*n2
f2 = a*n2 + b*n1

通过数学变形可直接推导结论，完全不需要动态规划数组：

• 第一步：f1 + f2 = (a + b)*(n1 + n2)，因此**f1+f2必须能被n1+n2整除**，设k=(f1+f2)/(n1+n2)，则a+b=k。
• 第二步：若n1≠n2，则f1 - f2 = (a - b)*(n1 - n2)，因此**f1-f2必须能被n1-n2整除**；若n1=n2，则必须满足f1=f2。
• 第三步：解出a=(k + (f1-f2)/(n1-n2))/2，b=(k - (f1-f2)/(n1-n2))/2，判断a和b是否为非负整数。

满足所有条件则返回1，否则返回0，时间复杂度O(1)，效率极高。

2. 仅存储实际访问的状态（哈希表） #

如果坚持用动态规划，注意递归过程中实际访问的(f1,f2)状态数量有限（每次递归数值递减，最多递归(f1+f2)/min(n1,n2)次），因此可以用哈希表存储已计算的状态，避免预分配大数组：

• 使用轻量级哈希表库（如uthash）或自行实现哈希表，每次计算前查询哈希表，不存在则计算后存入。
• 每次循环只需清空哈希表，无需遍历重置巨大数组。

示例代码片段（基于uthash）：

#include "uthash.h"

typedef struct {
    unsigned int f1;
    unsigned int f2;
    int val;
    UT_hash_handle hh;
} State;

State *memo = NULL;

// 查询状态
int get_memo(unsigned int f1, unsigned int f2) {
    State *s;
    HASH_FIND(hh, memo, &f1, sizeof(f1), s);
    if (s && s->f2 == f2) return s->val;
    return -1;
}

// 存储状态
void set_memo(unsigned int f1, unsigned int f2, int val) {
    State *s;
    HASH_FIND(hh, memo, &f1, sizeof(f1), s);
    if (s) {
        s->val = val;
        return;
    }
    s = malloc(sizeof(State));
    s->f1 = f1;
    s->f2 = f2;
    s->val = val;
    HASH_ADD(hh, memo, f1, sizeof(f1), s);
}

// 清空哈希表（每次循环调用）
void clear_memo() {
    State *current, *tmp;
    HASH_ITER(hh, memo, current, tmp) {
        HASH_DEL(memo, current);
        free(current);
    }
}

修改comida函数适配哈希表：

int comida(unsigned int f1, unsigned int f2) {
    if (f1 == 0 && f2 == 0) return 1;

    int val = get_memo(f1, f2);
    if (val != -1) return val;

    int res = 0;
    if (f1 >= n1 && f2 >= n2) res = comida(f1 - n1, f2 - n2);
    if (!res && f1 >= n2 && f2 >= n1) res = comida(f1 - n2, f2 - n1);

    set_memo(f1, f2, res ? 1 : 0);
    return res;
}

3. 时间戳标记替代全量重置（仅适用于输入有上限场景） #

若输入的f1,f2有明确上限（远小于2e9），可以用时间戳标记避免全量重置：

• 定义两个数组：memo存储时间戳，res_memo存储计算结果。
• 每次循环时timestamp加1，查询时判断memo[f1][f2]是否等于当前timestamp，不等于则视为未访问状态，计算后更新memo和res_memo。

这种方法避免了O(MAX²)的重置时间，但仅适用于输入范围可控的场景。

内容的提问来源于stack exchange，提问作者César Lozano