题目描述

给定一个n*m的方格阵，沿着方格的边线走，从左上角(0,0)开始，每次只能往右或者往下走一个单位距离，问走到右下角(n,m)一共有多少种不同的走法。

算法

递归

每次只能往右或往下走一个单位距离，因此返回表达式为zfg(i+1,j,n,m)+zfg(i,j+1,n,m)。

目标是得到所有可能的走法，只要索引i，j满足条件时就返回1，超出范围时返回0。

C++ 代码

#include <iostream>
using namespace std;

int zfg(int i, int j, int n, int m)
{
    if(i>n||j>m) return 0;
    if(i==n&&j==m) return 1;
    return zfg(i+1,j,n,m)+zfg(i,j+1,n,m);
}

int main()
{
    int n,m;
    scanf("%d%d", &n,&m);
    printf("%d", zfg(0, 0, n, m));

    return 0;
}