题意

沿n 乘 m的棋盘边界从左上角，只能向右或向下走到右下角的方案数

限制：n和m均不超过8

方法

递推

既然只能向右或者向下走，反过来说明一个位置要么从上方来，要么从左方来。切因为上一个点不同，所以这两个方向来的各不相同

定义$dp[i][j]dp[i][j]$ 表示从左上角走到第$ii$行,第$jj$列的方案数

那么它上方的格子的方案数为$dp[i-1][j]dp[i-1][j]$，它左方的格子的方案数为$dp[i][j-1]dp[i][j-1]$

有递推表达式 $dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]\; =\; dp[i-1][j]\; +\; dp[i][j-1]$，

因为n和m比较小，可以提前计算所有答案，每次询问时直接输出答案

从直观上看，就是递推时，一个格子的值等于它上方和它左方的值的和

代码

#include<bits/stdc++.h>
using namespace std;

int dp[10][10];

int main(){
    int n,m;
    dp[0][1] = 1; // 保证dp[1][1] 为 1
    for(int i = 1;i < 10;i++){
        for(int j = 1;j < 10;j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 递推式
        }
    }
    while(~scanf("%d %d",&n,&m)){
        printf("%d\n",dp[n+1][m+1]); // 直接输出答案
    }
    
    return 0;
}

复杂度分析

时间复杂度: 因为计算了所有答案，所以时间复杂度为$O(mn)O(mn)$

空间复杂度: 因为记录了所有答案所以空间复杂度为$O(mn)O(mn)$

递归+记忆化

注意到上面预处理了所有结果，但实际上可能要询问的并没有这么多

所以可以直接把$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]\; =\; dp[i-1][j]\; +\; dp[i][j-1]$转化为递归关系，其中任意一侧为0时达到了边界返回1

这样的话，有些结果会被重复计算，于是加上记忆化让每个格子最多被算一次

代码

#include<bits/stdc++.h>
using namespace std;

int dp[10][10];

int dfs(int i,int j){
    if(i == 0 || j == 0)return 1; // 边界
    if(dp[i][j])return dp[i][j]; // 记忆化
    return dp[i][j] = dfs(i-1,j)+dfs(i,j-1); // 储存结果
}

int main(){
    int n,m;
    while(~scanf("%d %d",&n,&m)){
        printf("%d\n",dfs(n,m)); // 调用递归
    }
    return 0;
}

复杂度分析

时间复杂度: 最坏情况所有格子被计算一次，$O(nm)O(nm)$

空间复杂度: 最坏情况会记忆所有格子，$O(mn)O(mn)$