首页 > 试题广场 >

走方格的方案数

[编程题]走方格的方案数

热度指数：136604 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的由 $n+1$ 条横线和 $m+1$ 条竖线组成的网格，共相交形成 $n \times m$ 个格点。
$\hspace{15pt}$ 现在，你从网格的左上角格点出发，只能沿着网格线向右或向下走，求解走到右下角格点的不同方案数。

输入描述:

在一行上输入两个整数 ，代表网格的行数和列数。

输出描述:

输出一个整数，代表不同的行走方案数。

示例1

输入

2 2

输出

说明

在这个样例中，所绘出的网格图如下图所示。

算法知识视频讲解

牛油果114514

可以使用递归解决，递归并不高效，穷尽了所有的可能，

不过思路很好理解，将大的问题分解成小的边界问题解决。

#include <stdio.h>

int walk(int x, int y, int xmax, int ymax);

int main() {
    int x, y;
    int plan;

    scanf("%d %d", &x, &y);
    plan = walk(0, 0, x, y);
    printf("%d", plan);
    return 0;
}

int walk(int x, int y, int xmax, int ymax) {
    int plan = 0;
    if (x < xmax) {
        plan += walk(x + 1, y, xmax, ymax);
    }
    if (y < ymax) {
        plan += walk(x, y + 1, xmax, ymax);
    }
    if (x = xmax && y == ymax) {
        return 1;
    }
    return plan;
}

发表于 2025-02-01 12:33:51 回复(1)

猪猪侠的飞天梦

利用动态规划来做最简单，时间复杂度最低

#include <stdio.h>
inline int func(int m, int n) {
    int map[100][100] = {0};
    for (int i = 0; i < n; i++) map[0][i] = 1;
    for (int i = 1; i < m; i++) map[i][0] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            map[i][j] = map[i - 1][j] + map[i][j - 1];
        }
    }
    return map[m - 1][n - 1];
}
int main() {
    int m = 0, n = 0;
    scanf("%d %d", &m, &n);
    printf("%d", func(++m, ++n));
    return 0;
}

编辑于 2023-12-16 20:24:58 回复(0)

彭洋a

#include <stdio.h>

int sum(int m,int n)

{

if(m==1&&n==1)

{

return 2;

}

else if(m==1||n==1)

{

if(m == 1)

{

return n+1;

}

else

{

return m+1;

}

return sum(m-1,n)+sum(m,n-1);

}

int main() {

int a, b;

while (scanf("%d %d", &a, &b) != EOF) {

int ret = sum(a,b);

printf("%d\n",ret);

}

return 0;

}

发表于 2023-10-13 23:45:42 回复(0)

Jackn

#include <stdio.h>

int f(int n,int m){
    if(n==0||m==0) return 1;
    return f(n-1,m)+f(n,m-1);
}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%d\n",f(n,m));
    return 0;
}
递归方法

发表于 2023-03-28 20:02:19 回复(0)

好久不见，最近好吗

#include <stdio.h>
#include <stdlib.h>
int ** malloc_planar_array_int(int row,int col)
{
int **p = NULL;
int i = 0;
p = (int**)malloc(sizeof(int *)*(row));
if(!p)
{
return NULL;
}
for(i = 0;i<row;i++)
{
p[i] = malloc(sizeof(int)*(col));
if(!p[i])
{
return NULL;
}
}
return p;
}

void free_planar_array_int(int **p,int row)
{
int i = 0;
if(!p) return;
for(i = 0;i<row;i++)
{
if(p[i])
{
free(p[i]);
p[i] = NULL;
}
}
free(p);
p = NULL;
}
int main()
{
int i,j,n,m;
int **dp = NULL;
while(scanf("%d%d",&n,&m)!=EOF)
{
dp = malloc_planar_array_int(n+1,m+1);
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||j==0)
dp[i][j]=1;
else
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
printf("%d\n",dp[n][m]);
free_planar_array_int(dp,n+1);
}
return 0;
}

发表于 2022-06-19 17:05:20 回复(0)

已注销

#include <stdio.h>
#define    N    100
int main()
{
    int dp[N][N],i,j,n,m;
    scanf("%d%d",&n,&m);
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            if(i==0||j==0)
                dp[i][j]=1;
            else
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}

发表于 2022-04-26 08:59:26 回复(0)

海饼干666

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int tmp = 0,cnt = 0;
    int rc[2] = {0,0};
    
    while(scanf("%d",&tmp) != EOF)
    {
        if(tmp != ' ' && tmp != '\n')
        {
            rc[cnt++] = tmp+1;
        }
        if(cnt == 2)
        {
            int **map = (int *)malloc(rc[0] * sizeof(int*));
            for(int i = 0; i < rc[0]; i++)
            {
                map[i] = (int *)malloc(rc[1] * sizeof(int));
                memset(map[i],0,rc[1]);
            }
            
            for(int j = 0; j < rc[1]; j++) map[0][j] = 1;
            for(int i = 0; i < rc[0]; i++) map[i][0] = 1;
            for(int i = 1; i < rc[0]; i++)
            {
                for(int j =1; j < rc[1]; j++)
                {
                    map[i][j] = map[i][j-1] + map[i-1][j];
                }
            }
            
            printf("%d\n",map[rc[0]-1][rc[1]-1]);
            cnt = 0;
        }
    }
    
    return 0;
}

发表于 2021-09-03 15:31:07 回复(0)

牛客415544593号

#include<stdio.h>

int path(a,b)
{
    if(a==0 || b==0)
        return 1;
    else
        return path(a-1,b)+path(a,b-1);
}

int main()
{
    int num1,num2;
    while(scanf("%d %d",&num1,&num2)!=EOF)
    {
        printf("%d\n",path(num1,num2));
    }
    return 0;
}

发表于 2021-08-17 23:18:01 回复(0)

牛客312540312号

#include<stdio.h>

int main()
{
int a, b;
while(scanf("%d %d",&a,&b) != EOF)
{
int c = 1, d = 1;
for(int i = 1; i <= a; i++)
{
c *= i;
}
for(int j = b + 1; j <= a + b; j++)
{
d *= j;
}
printf("%d\n", d/c);
}
}

发表于 2021-08-11 20:24:54 回复(0)