首页 > 试题广场 >

走方格的方案数

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

2 2

输出

说明

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

算法知识视频讲解

小陈也只是想要一个实习罢了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static int findWays(int m,int n){
        int[] rec=new int[n];
        rec[0]=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(j==0) rec[j]=rec[j];
                else if(i==0) rec[j]=rec[j-1];
                else rec[j]=rec[j-1]+rec[j];
            }
        }
        return rec[n-1];
    }

    public static void main(String[] args)throws IOException {
        //读入和输出的方式要注意，使用bufferedReader中的readLine可以很好知道是否到了末尾
        BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
        String line=null;
        while((line=bReader.readLine())!=null) {
            int n=Integer.valueOf(line.substring(0,line.indexOf(" ")));
            int m=Integer.valueOf(line.substring(line.indexOf(" ")+1));
            System.out.println(findWays(n+1, m+1));
        }
    }
}

发表于 2020-06-08 12:06:52 回复(1)

牛客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)

C++

yzbyzb

#include <iostream>
using namespace std;

int f(int a){
if(a==1) return 1;
return a*f(a-1);
}

int main(){
int n,m;
while(cin>>n>>m){
cout<<f(n+m)/f(n)/f(m)<<'\n';
}
}

发表于 2021-07-20 00:04:37 回复(0)

Python 3

来个offer叭！

get_str = input().split(' ')
n, m = int(get_str[0]), int(get_str[1])
# (n+1)*(m+1)的二维dp数组
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        # dp数组初始化
        # 原点时0种走法
        if i==0 and j==0:
            dp[i][j] = 0
        # 从原点向下走一步共1种走法
        # elif i==0 and j==1:
        # 这里可以考虑优化？当退到左边界或上边界时仅剩一种走法
        elif i==0:
            dp[i][j] = 1
        # 从原点向右走一步共1种走法
        # elif i==1 and j==0:
        elif j==0:
            dp[i][j] = 1
        # [i][j]点的走法=左边一个点走法+上面一个点的走法
        # 即：dp[i][j] = dp[i-1][j] + dp[i][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][m])

发表于 2022-07-30 17:46:31 回复(0)

C++

李艳飞

#include <iostream>

using namespace std;

int fun(int num);

int main()
{
    int m=0, n=0;
    cin>>m>>n;
    cout<<fun(n+m)/(fun(m)*fun(n))<<endl;
    return 0;
}

int fun(int num)
{
    int sum=1;
    for(int i=2;i<=num;i++)
    {
        sum*=i;
    }
    return sum;
}

发表于 2022-05-12 20:49:29 回复(1)

Java

笨糕sama

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()){

            int n = sc.nextInt();
            int m = sc.nextInt();
            int countUp = n;
            int countDown = n+m;
            int num = n;
            int zzz = n+m;
//            for (int a=n;a>1;--a){
//                    countUp = countUp*(a-1);
//                    countDown = countDown*(--countDown);
//            }
            while (num>1){
                countUp = countUp*(num-1);
                countDown = countDown*(zzz-1);
                num--;
                zzz--;
            }
            int count = countDown/countUp;

            System.out.println(count);
        }

    }
}

发表于 2021-11-26 01:19:31 回复(0)

Java

AlexWenn

方法1：
//数学方法，相当于一共要走（n+m)步，其中往右走要走n步，问题是在（n+m）步里哪些步是
//往右走。相当于在（n+m）个中取m个有多少种组合的问题。
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();

            System.out.println(combination(n, n+m));
        }
        sc.close();
    }

    public static int combination(int m, int n){//排列C(m,n)
        int above = factorial(n);
        int below = factorial(n-m) * factorial(m);
        return above / below;
    }

    public static int factorial(int n){//阶乘
        if(n>1){
            return n*factorial(n-1);
        }
        return n;
    }
}

方法2：把问题解法定为f(n,m),从左上角第1个点开始，如果往右走1步，剩下的问题就变成了f(n-1,m); 如果一开始往下走一步，剩下的问题就变成f(n,m-1), 一直递归，就有了f(n,m)=f(n-1,m)+f(n,m-1)。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(count(m,n));
        }

        sc.close();
    }

    public static int count(int m, int n){

        if(m==0 || n==0){
            return 1;
        }

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


    }

}

发表于 2021-10-27 10:46:50 回复(0)

彩虹桥的梦

动态规划：

while True:
    try:
        n,m = map(int, input().split())

        dp = [[1 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                temp = dp[i-1][j-1]*2
                temp1 = 0
                temp2 = 0

                for k in range(i-1):
                    temp1 += dp[k][j-1]
                for l in range(j-1):
                    temp2 += dp[i-1][l]
                dp[i][j] = temp+temp1+temp2
        print(dp[n][m])
    except:
        break

发表于 2021-01-26 15:57:35 回复(0)

牛客464555119号

C++，经典递归系列

#include <bits/stdc++.h>
using namespace std;
int count(int n, int m){
    if(n==0||m==0)
        return 1;
    return count(n-1,m)+count(n,m-1);
}
int main(){
    int n,m;
    while(cin>>n>>m){
        cout<<count(n,m)<<endl;
    }
    return 0;
}

发表于 2020-08-05 13:58:33 回复(0)

Python

^o^201903061215958

思路：动态规划

import sys

def f(n,m):
    if min(n,m)==1:
        return 1 + max(n,m)
    else:
        return f(n,m-1) + f(n-1,m)

for s in sys.stdin:
    s = s.strip().split(" ")
    r = f(int(s[0]), int(s[1]))
    print(r)

编辑于 2020-06-07 22:53:17 回复(0)

C/C++

WZ_Dale

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int m, n;
    while(cin >> m >> n){
        vector<vector<int>> F(m + 1, vector<int>(n + 1, 1));
        for(int i = 1; i < m + 1; ++i){
            for(int j = 1; j < n + 1; ++j){
                F[i][j] = F[i - 1][j] + F[i][j - 1];
            }
        }
        cout << F[m][n] << endl;
    }
    return 0;
}

发表于 2020-06-04 09:49:41 回复(0)

南少201911241210480

#include<iostream>
(720)#include<vector>
using namespace std;
int main()
{
    int dfs(int n,int m);
    int n,m;
    while(cin>>n>>m)//n是列，m是行
    {
       vector<vector<int>>dp(m+1,vector<int>(n+1,1));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
               dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        cout<<dp[m][n]<<endl;
        //cout<<dfs(n,m)<<endl;
    }
}
int dfs(int n,int m)
{
    if(m==0&&n==0)
        return 1;
    if(m>=0&&n>=0)
    {
        return dfs(n-1,m)+dfs(n,m-1);
    }
    return 0;
}

里面两种解法，一个dp,一个dfs

发表于 2020-04-16 12:08:18 回复(1)

C/C++

牛客227521256号

#include <stdio.h>
(737)#include <string.h>

int n,m,sum,chess[128][128];

void DFS(int x,int y)    //深度优先搜索
{
	chess[x][y] = 1;
	if(x==m && y==n)
	{
		sum++;
		chess[x][y]=0;	
		return;
	}
	if(chess[x+1][y]==0 && x+1<=m)
		DFS(x+1,y);
	if(chess[x][y+1]==0 && y+1<=n)
		DFS(x,y+1);
	chess[x][y]=0;	
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF)
    {
        DFS(0,0);
        printf("%d\n",sum);
        sum =0;
        memset(chess,0,sizeof(chess));
    }
    return 0;
}

发表于 2020-04-14 23:13:29 回复(0)

牛客344658091号

这题的输入是坑呐~~~

明明说的输入两行，结果确是一行用空格隔开。。。

输出需要说明的是：需要它能够持续跑完所有的测试用例，也就是说需要一次输入一次输出，然后继续接受参数，继续输出，以此类推

发表于 2020-03-30 23:12:50 回复(0)

阿米诺斯

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
            int m=sc.nextInt();
            int n=sc.nextInt();
            int t=m+n;
            int s=m>n?n:m;
            System.out.println(cal(t,s));
        }
    }
    public static int cal(int i,int j){
        if(j==0) return i;
        int a=1,b=1;
        for(int z=0;z<j;z++){
            a*=i-z;
            b*=z+1;
        }
        return a/b;
    }
}

发表于 2020-03-03 17:39:09 回复(0)

C/C++

牛客472374344号


	//可以用递归解决，但是最后的函数出口应该是n = 1或者m = 1的情况

//另外可以用动态规划方法解决（如下）
#include<iostream>
using namespace std;

int main(){
    int n = 0, m = 0;
    while(cin>>n, cin>>m){
        int dp[n+1][m+1];
        for(int i =0;i<n+1;i++){
            for(int j = 0;j<m+1;j++){
                if(i == 0 && j == 0){
                    dp[i][j]= 1;
                }else if(i == 0 && j != 0){
                    dp[i][j] = dp[i][j-1];
                }else if(i != 0 && j == 0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}

发表于 2020-03-02 12:28:32 回复(0)

Python

谢小橙

def walk(n,m):
    if n==0&nbs***bsp;m==0:
        return 1
    return walk(n-1,m)+walk(n,m-1)

while True:
    try:
        l=input().split()
        n=int(l[0])
        m=int(l[1])
        print(walk(n,m))
    except:
        break

用递归去做，通项公式为：f(n,m)=f(n-1,m)+f(n,m-1)，假设终点坐标为（n,m）。边界条件：当n==1或者m==1时，只有1种走法。

发表于 2020-02-21 16:28:44 回复(0)

彼岸浮灯201907121905423

while True:
    try:
        a,b = map(int, raw_input().split())
        a += 1
        b += 1
        #b = int(raw_input())
        dp = [[0]*(b+1) for _ in range(a+1)]
        dp[0][1] = 1
        for i in range(1,a+1):
            for j in range(1,b+1):
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
        print dp[-1][-1]
    except:
        break

发表于 2019-07-16 15:53:47 回复(0)

那年，那些年

动态规划且额外空间O(min(m,n))

int numofstep(int max, int min)
{
    if (max < min)
        swap(max, min);
    vector<int> arr(min+1, 1);
    for (int i = 1; i <= max; ++i)
        for (int j = 1; j <= min;++j)
            arr[j] = arr[j] + arr[j - 1];
    return arr[min];
}
int main()
{
    int m, n;
    while (cin >> m >> n)
        cout << numofstep(m, n) << endl;
    return 0;
}

发表于 2019-07-11 15:13:34 回复(0)

Hmmmmmmm_y

#include <bits/stdc++.h>
 using namespace std;
//void dfs()
 int main()
 {
     int n,m;
     while(cin>>n>>m)
     {
         vector<vector<int> > dp(m+1,vector<int>(n+1,0));
         dp[0][0]=1;
         for(int i=1;i<n+1;i++)
             dp[0][i]=1;
         for(int j=1;j<m+1;j++)
             dp[j][0]=1;
         for(int i=1;i<m+1;i++)
         {
             for(int j=1;j<n+1;j++)
             {
                 dp[i][j] = dp[i-1][j]+dp[i][j-1];
             }
         }
         int res = dp[m][n];
         cout<<res<<endl;
     }
         system("pause");
         return 0;
 }

发表于 2018-08-06 13:01:52 回复(0)