路径计数算法调试求助：二维网格路径数计算代码问题

我正在解决二维网格中的路径计数问题，已知网格数组及尺寸N(y)、M(x)，需统计合法路径的数量。我编写了动态规划代码，核心逻辑为：若当前网格值为1，则累加其下方三个相邻网格的值（边界情况做对应处理）。但多次尝试均失败，已卡壳两天，附上示例输入输出及代码片段，请问我遗漏了什么？

示例输入输出 #

输入 #

5 5
1 0 1 0 1
0 0 1 1 1
1 0 1 0 0
0 1 1 0 1
1 0 1 0 1

输出 #

9

代码片段 #

//x width = 1
if(m==1)
{
    for(int i=0;i<n;i++)
    {
        sum+=arr[i][0];
    }
    if(sum == n)
        sum = 1;
    else
        sum = 0;
    printf("%lld\n", sum);
    return 0;
}

//y length = 1
if(n==1)
{
    for(int j=0;j<m;j++)
    {
        sum+=arr[0][j];
    }
    printf("%lld\n", sum);
    return 0;
}

//x, y >=2 case
for(int i=n-2;i>=0;i--)
    for(int j=0;j<m;j++)
    {
        if(arr[i][j]==1)
        {
        if(j==0)        //left end
            arr[i][j] = arr[i+1][j]+arr[i+1][j+1];
        else if(j==m)   //right end
            arr[i][j] = arr[i+1][j-1]+arr[i+1][j];
        else            //middle
            arr[i][j] = arr[i+1][j-1]+arr[i+1][j]+arr[i+1][j+1];
        }
    }

关键错误点 #

• 右边界判断错误：数组下标从0开始，右边界的正确判断应为j == m-1，而非j == m，当前写法会触发数组越界，导致计算结果异常。
• 初始行未正确初始化：动态规划的初始状态应为最后一行（i = n-1）的每个网格，若网格值为1则路径数为1，为0则为0。你直接使用原数组值进行后续计算，若最后一行存在0，会导致后续路径统计错误。
• 单行（n==1）逻辑错误：当y长度为1时，只有所有网格值均为1时，才存在1条合法路径；否则路径数为0。但当前代码直接累加网格值，逻辑完全错误，应和m==1的情况保持一致。
• 数据类型溢出：路径数可能快速增长，数组arr需定义为long long类型，若使用int会导致累加时溢出，结果失真。

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