使用备忘录法求解网格旅行者问题时(18,18)输入返回异常值求助

核心问题：整数溢出 #

18x18网格的路径数是2333606220，而C语言中int类型的最大值通常是2147483647（32位有符号整数），计算结果超出了int的范围，导致有符号整数溢出，最终得到负数结果。

修复步骤 #

• 替换整数类型：将所有涉及路径数存储和计算的变量类型从int改为long long，long long的最大值是9223372036854775807，足够容纳18x18甚至更大网格的路径数。
• 调整数组初始化与函数返回值：对应修改数组类型、函数参数和返回值类型。

修复后的代码 #

#include <stdio.h>

long long grid(int row, int col, int a, long long arr[][a]) {
    if (arr[row][col] != -1) {
        return arr[row][col];
    }
    arr[row][col] = grid(row-1, col, a, arr) + grid(row, col-1, a, arr);
    return arr[row][col];
}

int main() {
    int row = 18, col = 18;
    long long arr[row][col];
    
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (i == 0 || j == 0) {
                arr[i][j] = 1;
            } else {
                arr[i][j] = -1;
            }
        }
    }
    
    int a = col;
    printf("%lld", grid(row-1, col-1, a, arr));
    return 0;
}

额外说明 #

• 若需处理更大的网格（比如30x30），long long也可能不够，此时可考虑使用无符号类型unsigned long long，或者引入大整数库，但18x18的场景下long long完全足够。
• 整数溢出在C语言中属于未定义行为，数值计算场景必须提前评估结果范围并选择合适的类型。

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