方格走法_牛客博客

题解：

考察点： 深度优先搜索，动态规划

易错点：

方格的大小为 $X \times Y$ ，但是格点数却为 $(X+1) \times (Y+1)$

方法一：深度优先搜索

选用深度优先搜索是解决这类题目最直观的思路，因为格点只能往下走或者往右走，所以对于方格中位置 $(x,y)$ ，一定只能由它的上方位置和左边位置走过来。那么令 $dfs(x,y)$ 为走到位置 $(x,y)$ 的方案数，则根据加法原理，它一定由左边位置的方案数加上上方位置的方案数。同时记得处理一下边界情况，也就是递归结束的条件，对于位置 $(1,1)$ ，它的方案数一定为1，而对于越界的位置，方案数一定为0

#include "bits/stdc++.h"
using namespace std;
int n,m;
int dfs(int x,int y){
    if(x==0||y==0||x==n+1||y==m+1) return 0;
    if(x==1||y==1) return 1;
    return dfs(x-1,y)+dfs(x,y-1);

}
int main()
{
    scanf("%d%d",&n,&m);
    ++n,++m;
    printf("%d\n",dfs(n,m));
    return 0;
}

方法二：动态规划

方法一虽然很直观，但时间复杂度很高，是指数级的时间复杂度，原因是因为很多中间结果都要重新计算，如果能将中间结果存下来，而不需要每次使用的时候都要重新去计算，则可以大大降低复杂度。动态规划就是基于这样一种思想，令 $dp(i,j)$ 表示坐标 $(i,j)$ 的方案数，则根据方法一的推理过程， $dp(i,j)=dp(i-1,j)+dp(i,j-1)$ 。经过空间换时间优化之后，时间复杂度降为 $O(n \times m)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=12;
int dp[maxn][maxn];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    ++n,++m;
    dp[1][1]=1;
    for(int i=2;i<=m;i++) dp[1][i]=1;
    for(int i=2;i<=n;i++) dp[i][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
    printf("%d\n",dp[n][m]);
    return 0;
}