题解 | #走方格的方案数#

#include <stdio.h>

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) { 
        int dp[a+1][b+1];
        dp[0][0]=1;
        for(int i=0;i<=a;i++)
        {
            for(int j=0;j<=b;j++)
            {
                if((i!=0&&j==0)||(i==0&&j!=0))
                {
                    dp[i][0]=1;
                    dp[0][j]=1;
                    continue;
                }
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        printf("%d\n", dp[a][b]);
    }
    return 0;
}

使用动态规划解题，设dp[i][j]为到达坐标（i,j）处的走法。通过任意选一点坐标稍微研究下，可以得到

dp[i][j]=dp[i-1][j-1]+dp[i][j-1](i!=0或j!=0);

若i=0或者j=0的坐标，由于题目规定只能向下或者向右，且不能返回，所以这些点的走法就只能有一种，即

dp[0][j]=1;

dp[i][j]=1;

这道题就顺利解决了