简单动态规划问题（寻找路径条数）

Question

问题遇到的现象和发生背景

蓝桥杯上的题

视频链接：https://www.bilibili.com/video/BV1qE411E7UK?p=3

问题相关代码，请勿粘贴截图

#include <stdio.h>

int main()
{
    long f[5][5]={0};
    int i,j;
    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
            {
                if(i == 0 and j == 0) //递推边界1 f[0][0]=1
                    f[0][0] = 1;
                else if(i == 0 and j > 0)//递推边界2，x=0时；
                    f[0][j] = f[0][j - 1];
                else if(i > 0 and j == 0)//递推边界3，y=0时；
                    f[i][0] = f[i - 1][0];
                else
                    f[i][j] = f[i - 1][j] + f[i][j - 1];//递推核心
            }
        printf("%d",f[4][4]);
        return 0; 
}

运行结果及报错内容

运行结果打印出的是70 而官方给出的答案却是是35

我的解答思路和尝试过的方法

在这个问题中，不管是上面还是左边的字都可以接上下一个字，所以问题就转化成了“从起点（0，0）开始，移动至终点（4，4）有可以有多少条路线”.所以根据动态转移方程f[i][j] = f[i - 1][j] + f[i][j - 1]写出了以上代码。

Answer 1

这一道题很容易被误认为机器人路径问题，但你仔细看看这个题目，这个是4行5列，你用的是5行5列的，应该用4行4列的。