题目描述

运用函数递归

算法1

从(0,0)开始走，直到走到(m,n)，成功一次走法就多一个。
注意边界

C++ 代码

#include <iostream>

using namespace std;
int n, m;
int res;

void f(int x, int y){
    if(x==n && y==m) res++;
    else{
        if(x<n) f(x+1, y);
        if(y<m) f(x, y+1);
    }
}

int main(){
    cin >> n >> m;
    f(0, 0);

    cout << res << endl;

    return 0;
}

算法2

(m,n)的走法数量等于(m-1,n)的走法加上(m,n-1)的走法

C++ 代码

#include <iostream>

using namespace std;

int f(int n, int m){
    if(n>=0 && m>=0){
        if(n==0 || m==0) return 1;  //如果n=0或者m=0，那么只有一种走法
        return f(n-1, m) + f(n, m-1);
    }
}

int main(){
    int n, m;
    cin >> n >> m;

    cout << f(n, m) << endl;

    return 0;
}