P8707 走方格 题解

· · 题解

这是一道典型的动态规划题目，建议先尝试 P1002。

设 f(x,y) 表示到格子 (x,y) 有多少走法，则易知 f(1,1)=1。而每一个格子（行、列号均为偶数或行、列号均为 1 除外）都可以由它上面和左边的格子走来，所以可以得到状态转移方程：

f(x,y)=f(x-1,y)+f(x,y-1)

其中 x,y 满足 x,y 不均为偶数，并且 x,y 不均为 1。

而对于每一对 x,y 均为偶数，有 f(x,y)=0。

因此我们很容易得出以下代码：

#include <iostream>
using namespace std;
int f[31][31];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    f[1][1]=1;//边界：f(1,1)=1
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if((i&1||j&1)&&(i!=1||j!=1))//i,j不均为偶数，且i,j不均为1
                f[i][j]=f[i-1][j]+f[i][j-1];//状态转移
    printf("%d",f[n][m]);
    return 0;
}