首页 > 试题广场 >

走方格的方案数

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

2 2

输出

说明

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

算法知识视频讲解

Java

牛客916838684号

对角线多一个格子，走法✖2，侧面多一个格子走法+1，于是有最短对角线格子✖2加上侧面格子。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int min = Math.min(m,n);
        System.out.println(min*2+m+n-2);
    }
}

发表于 2025-09-27 15:29:49 回复(0)

Java

我好中意你啊

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

while (in.hasNextInt()) {

int n = in.nextInt();

int m = in.nextInt();

System.out.println(comb(n + m, n));

// System.out.println(dtgh(n, m));

}

/**

* 组合数学

* 路径需要向下移动 n 次和向右移动 m 次，总共有 n + m 步，从中选择 n 次向下（或 m 次向右）的方案数即为组合数 C(n + m, n)

* C(n + m, n) = (n + m)! / (n! * m!)

* 利用组合数的对称性 C(a, b) = C(a, a - b) 来减少计算量

private static int comb(int a, int b) {

if (b > a - b) {

b = a - b;

}

long result = 1;

// 通过循环逐步计算分子和分母的乘积，避免直接计算大阶乘

for (int i = 1; i <= b; i++) {

result = result * (a - b + i) / i;

}

return (int) result;

}

/**

* 动态规划

* 走向(i,j)位置的前一步只能从(i-1,j)或(i,j-1)的位置出发

private static int dtgh(int n, int m) {

int[][] dp = new int[n + 1][m + 1];

for (int i = 0; i <= n; i++) {

dp[i][0] = 1;

}

for (int j = 0; j <= m; j++) {

dp[0][j] = 1;

}

for (int i = 1; i <= n; i++) {

for (int j = 1; j <= m; j++) {

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

}

return dp[n][m];

}

发表于 2025-03-28 10:36:08 回复(0)

Java

YonSen

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m;
        n = sc.nextInt() + 1;
        m = sc.nextInt();
        long[] dp = new long[n];
        Arrays.fill(dp, 1);
        fn(dp, m);
    }

    public static void fn(long[] dp, int m) {
        for (int i = 0; i < m; ++i) {
            for (int j = 1; j < dp.length; ++j) {
                dp[j] += dp[j - 1];
            }
        }
        System.out.println(dp[dp.length - 1]);
    }
}

可以用滚动数组

发表于 2024-06-25 12:50:58 回复(0)

Java

欢哥你是大神

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        //格子数+1是线
        int [][]a=new int[m+1][n+1];
        for(int i =0;i<m+1;i++){
            a[i][0]=1;
        }
        for(int i =0;i<n+1;i++){
            a[0][i]=1;
        }
        for(int i =1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                a[i][j]=a[i-1][j]+a[i][j-1];
            }
        }
       System.out.print(a[m][n]);
    }
}

编辑于 2024-04-11 10:42:03 回复(0)

Java

牛客68977316号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] dp = new int[m][n];
        dp[0][0] = 2;
        
        for(int i = 1 ;i < n;i++){
            dp[0][i] = dp[0][i-1] + 1;
        }

        for(int i = 1 ;i < m;i++){
            dp[i][0] = dp[i-1][0] + 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];
            }
        }

        System.out.print(dp[m-1][n-1]);

    }
}

编辑于 2024-04-02 15:28:24 回复(0)

Java

若是此时初见

f(i,j)表示横向i格竖向j格的方格走法方案数量

走向(i,j)位置的前一步只能从(i-1,j)或(i,j-1)的位置出发

容易得到f(i,j)=f(i-1,j)+f(i,j-1)

该问题分解成求解子问题，递归求解子问题得到最终解

方式1 动态规划

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //f(i,j)表示横向i格竖向j格的方格走法方案数量
        //走向(i,j)位置的前一步只能从(i-1,j)或(i,j-1)的位置出发
        //容易得到f(i,j)=f(i-1,j)+f(i,j-1)
        //该问题分解成求解子问题，递归求解子问题得到最终解
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i <= m; i++) {
            dp[i][0] = 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];
            }
        }
        System.out.println(dp[m][n]);
    }
}

方式2 递归求解

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        //f(i,j)表示横向i格竖向j格的方格走法方案数量
        //走向(i,j)位置的前一步只能从(i-1,j)或(i,j-1)的位置出发
        //容易得到f(i,j)=f(i-1,j)+f(i,j-1)
        //该问题分解成求解子问题，递推得到最终解
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        System.out.println(getSolutions(m, n));
    }

    public static int getSolutions(int i, int j) {
        if(i==0 || j==0) return 1;
        return getSolutions(i - 1, j) + getSolutions(i, j - 1);
    }
}

编辑于 2024-01-29 15:26:57 回复(0)

Java

记不得许多类库

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int min = n<m? n:m;
            int s = 1;
            for(int i=0;i<min;i++){
                s=s*(n+m-i)/(1+i);
            }
            System.out.println(s);
    }
}

发表于 2023-12-12 23:32:09 回复(0)

Java

牛客287768837号

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNextInt()) { // 注意 while 处理多个 case

int a = in.nextInt();

int b = in.nextInt();

int[][] f = new int[a+1][b+1];

for(int i=0; i<=a; i++){

for(int j=0; j<=b; j++){

if(i==0 | j==0){

f[i][j] = 1;

continue;

}

f[i][j] = f[i-1][j] + f[i][j-1];

}

System.out.println(f[a][b]);

}

发表于 2023-10-25 11:47:05 回复(0)

Java

小飞快跑

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        //动态规划算法
        int a = in.nextInt();
        int b = in.nextInt();
        int num = jisuan(a,b);
        System.out.print(num);
    }

    public static int jisuan(int a,int b){
           if(a==0 || b ==0){
              return 1;
           }           
            return jisuan(a-1,b)+jisuan(a,b-1);           
    }
}动态规划算法，说到底就是拆解成最小不能再拆的一种场景，这种场景就是a ==0 或者 b==0 ,这种情况就只有一种走法，然后相加即可得到答案

发表于 2023-09-05 11:06:34 回复(0)

Java

W_wwwww

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

while (scan.hasNext()) {

int n = scan.nextInt();

int m = scan.nextInt();

System.out.println(med(n, m));

}

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

//当m==1或者n==1的时候总的路径数为m+n

if ((n == 1 && m >= 1) || (m == 1 && n >= 1)) {

return n + m;

}

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

}

发表于 2023-08-16 04:15:48 回复(0)

Java

练习时长两年半的太平湖水怪很理智

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str=br.readLine())!=null){
            String[] strArr=str.split(" ");
            int n = Integer.parseInt(strArr[0]);
            int m = Integer.parseInt(strArr[1]);
            // dp表示第i*j棋盘的走法数
            int[][] dp=new int[m+1][n+1];
            // 初始化第1行的值，不含第0列
            for(int i=1;i<=n;i++) dp[1][i]=i+1;
            // 初始化第1列的值，不含第0行
            for(int i=1;i<=m;i++) dp[i][1]=i+1;
            // i、j行列的值等于i-1、j行列的值+i、j-1行列的值
            for(int i=2;i<=m;i++){
                for(int j=2;j<=n;j++){
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }
            }
            System.out.println(dp[m][n]);
        }
    }
}

发表于 2023-07-11 17:44:58 回复(0)

Java

SUMMERENT

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] dp = new int[n+1][m+1];
        for(int i = 0; i <= n; i++){
            for(int j = 0;j <= m; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }   
            }
        }
        System.out.println(dp[n][m]);
    }
}

发表于 2023-06-08 11:34:15 回复(0)

Java

YUIFEI

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static int count = 0;
    private static int max_x;
    private static int max_y;

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

        goAhead(0, 0);
        System.out.print(count);
    }

    private static void goAhead(int x, int y) {
        if (x > max_x || y > max_y) {
            return;
        }
        if (x == max_x && y == max_y) {
            count++;
            return;
        }
        goAhead(x+1, y);
        goAhead(x, y+1);
    }
}

发表于 2023-05-09 10:12:08 回复(0)

Java

1234_

import java.util.Scanner;

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

        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] map = new int[n+1][m+1];
            for (int i = 0; i <= n; i++) {
                map[i][0] = 1;
            }
            for (int i = 0; i <= m; i++) {
                map[0][i] = 1;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    map[i][j] = map[i - 1][j] + map[i][j - 1];
                }
            }
            System.out.println(map[n][m]);
        }
    }
}

发表于 2023-03-08 09:30:31 回复(0)

Java

炮炮小明

import java.util.Scanner;

/**
 * 请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
 * 注：沿棋盘格之间的边缘线行走
 *
 * 数据范围： 1 ≤ n,m ≤ 8
 *
 * 输入描述：
 * 输入两个正整数n和m，用空格隔开。(1≤n,m≤8)
 *
 * 在第一步时可以选择向右或者向下，只需要当前的路径选择上加上(n,m−1)和(n−1,m)的矩阵路径选择即可
 */
public class HJ91_dp走方格 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[][] dp=new int[n+1][m+1];
        for (int i = 0; i <=n ; i++) {
            dp[i][0]=1;
        }
        for (int i = 0; i <=m ; i++) {
            dp[0][i]=1;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        System.out.println(dp[n][m]);
    }
}

发表于 2022-08-26 15:37:40 回复(0)

Java

牛客318200376号

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        /*if(m==1 || n==1){
            System.out.println(1);
        }*/
        int[][] dp = new int[m+1][n+1];
        dp[0][0] = 1;
        
        /*i>0 j>0
        dp[i][j] = dp[i-1][j]+dp[i][j-1];
        //i=0 j>0
        dp[i][j] = 1;
        //i>0 j=0
        dp[i][j] = 1;*/
        for(int i=0;i<m+1;i++){
            for(int j=0;j<n+1;j++){
                if(i==0){
                    dp[i][j] = 1;
                }else if(j==0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        System.out.println(dp[m][n]);
    }
}

简单动态规划。注意走的方案，不是从格子到格子，是从格子的顶点到顶点

发表于 2022-08-01 21:38:17 回复(0)

Java

刘阳辉

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int count = count(n + 1, m + 1);
System.out.println(count);
}

public static int count(int n, int m) {
if (n == 1 || m == 1) {
return 1;
}
return count(n - 1, m) + count(n, m - 1);
}
}

发表于 2022-07-10 14:39:36 回复(0)

Java

醉饮荷风

import java.util.Scanner;

// 方法一：递归法，退出条件，有0
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] intArrys = new int[2];
while (scanner.hasNext()) {
for (int i = 0; i < 2; i++) {
intArrys[i] = Integer.parseInt(scanner.next());
}
break;
}
System.out.println(getNum(intArrys[0], intArrys[1]));
}

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

发表于 2022-06-17 14:11:57 回复(0)

Java

mysteries

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(walk(a,b));
        }
    }
    private static int walk(int n, int m) {
        // 定义二位dp数组dp[i,j] = dp[i-1,j]+dp[i,j-1];
        int[][] dp = new int[n + 1][m + 1];
        // base case
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 1;
        }
        // 递推
        for (int i = 1;i <= n;i++){
            for(int j = 1;j<= m ;j++){
                dp[i][j] = dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[n][m];
    }
}

发表于 2022-05-29 17:27:09 回复(0)