首页 > 试题广场 >

网格走法数目

[编程题]网格走法数目

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

有一个 X*Y 的网格，小团要在此网格上从左上角到右下角，只能走格点（也即格子的顶点）且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数 int x , int y ，请返回小团的走法数目。

数据范围： $1 \le x,y \le 10 \$

输入描述:

输入包括一行，逗号隔开的两个正整数x和y，取值范围[1,10]。

输出描述:

输出包括一行，为走法的数目。

示例1

输入

3 2

输出

算法知识视频讲解

hzwaxx

#include<iostream>
using namespace std;
int step(int m,int n){
    if(m == 0 || n == 0)
        return 1;
    return step(m - 1,n) + step(m,n -1);
}
int main(){
    int x,y;
    cin >> x >> y;
    cout << step(x,y) <<endl;
}

发表于 2017-08-26 15:21:07 回复(2)

您有一封offer请查收

注意是从网格点走。

发表于 2017-08-07 20:07:47 回复(9)

Java

指offer的剑在哪？

这是一个典型的递归算法问题，因为每次走法必须是往右或者是往下，因此不管是到达那个点，它的必经之路一定是它上方或者左方相邻的那个点，因此可以得出一个递归表达式：f[m][n]=f[m-1][n]+f[m][n-1]；这个递归表达式的条件为m,n都不为0的时候，除了这个表达式还需要写出一个已知条件，f[0][0] = 0;f[{1->m}][0] = 1;f[0][{1->n}] = 1;这样就可以解出最终f[m][n]的值了

import java.util.Scanner;

public class Main {
	
	//网格走法数目
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		int m,n;
		m = in.nextInt();
		n = in.nextInt();
		int f[][] = new int[11][11];
		f[0][0] = 0;
		for(int i=0; i<=m; i++)
			f[i][0] = 1;
		for(int i=0; i<=n; i++)
			f[0][i] = 1;
		for(int i=1; i<=m; i++){
			for(int j=1; j<=n; j++)
				f[i][j] = f[i-1][j] + f[i][j-1];
		}
		System.out.print(f[m][n]);
	}
}

发表于 2017-08-31 11:47:06 回复(9)

Python

R_12

s=input().split()
down=int(s[0])
right=int(s[1])
ruselt=1
def popo(n):
    res=1
    while n!=1:
        res*=n
        n-=1
    return res
print(popo(down+right)//popo(right)//popo(down))

发现没人这么做，其实无非是向下几次，向右几次的组合，算一下组合数就好了

发表于 2017-08-31 16:41:47 回复(8)

C/C++

卷积神经网络哦

非常经典的动态规划做过很多变种这个是最简单的类型
要注意题目的意思 x y是格点所以都要加一

#include<iostream>
using namespace std;
int dp[15][15];
int main(){
    int x, y;
    scanf("%d%d", &x, &y);
    for(int i = 1; i <= x + 1; i++) dp[i][1] = 1;
    for(int i = 1; i <= y + 1; i++) dp[1][i] = 1;
    for(int i = 2; i <= x + 1; i++)
        for(int j = 2; j <= y + 1; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    printf("%d\n", dp[x+1][y+1]);
}

发表于 2018-09-25 21:38:35 回复(0)

路人43

//先点赞再看！来个清晰容易理解的！！！

#include<iostream>

using namespace std;

把网格看做二维坐标，向下为正，向右为正：

设f(m,n)代表从坐标（0,0）到坐标（m,n）的移动方法，则

f(m,n)=f(m-1,n)+f(m,n-1)

开始为f(0,0)=0,f(0,1)=1,f(1,0)=1

进行递归运算,退出条件就是m,n至少有个为0，否则就要继续递归运算。

int get_ways(int x,int y){

//if(x==0 &&y==0) return 0;

if(x==1 &&y==0) return 1;

if(x==0 &&y==1) return 1;

if (x==0) return get_ways(x, y-1);

if (y==0) return get_ways(x-1, y);

else

return get_ways(x-1,y)+get_ways(x,y-1);

}

int main(){

int X,Y;

cin>>X>>Y;

cout<<get_ways(X,Y);

return 0;

}

发表于 2017-08-14 16:31:57 回复(8)

一匹努力的千里马

100%ac 这应该是最经（jian）典(dan)的动态规划问题了

‘---’---‘
‘---’---‘
‘---’---‘
’---‘---’
对于 x,y的网格，那么应该有向x+1,y+1节点数。
fcount代表到达当前的节点的可能的方法数。
初始化：最上面的和最左边的应该只有一种方法。fcount[i][0]=1; fcount[0][i]=1
更新：中间的应该是从左边到或者从上面到达的。所以fcount[i][j] = fcount[i-1][j] + fcount[i][j-1]
最后输出最右下角的值

import java.util.*;


public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        int[][] fcount = new int[x+1][y+1];
        
        for(int i = 0 ; i <= x;i++) {
            fcount[i][0] = 1;
        }
        for(int i = 0; i <= y;i++) {
            fcount[0][i] = 1;
        }
        
        for(int i = 1;i <= x;i++) {
            for(int j = 1;j <= y;j++) {
                fcount[i][j] = fcount[i-1][j] + fcount[i][j-1];
            }
        }
        
        System.out.println(fcount[x][y]);
    }
}

发表于 2018-05-10 10:34:34 回复(2)

Rnanprince

排列组合，C(n+m,n)或者C(n+m,m)，例如2,3，到终点一共走了5步，其中向右2步，5步中和选择2个，即C(5,2)

import java.util.Scanner;
public class Main{

// 直接C(n+m,n)
public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 long n = sc.nextInt();
 long m = sc.nextInt();
 System.out.println(recursive_C(n + m, m));
 }
 // C(n,m)
 public static long recursive_C(long n, long m) {
 return getNFactorial(n) / getNFactorial(m) / getNFactorial(n - m);
 }
 // n!
 public static long getNFactorial(long n) {
 if (n == 0) {
 return 1;
 }
 return n * getNFactorial(n - 1);
 }
 }

编辑于 2018-04-19 22:03:30 回复(3)

C/C++

stubsx

其实从数学上分析就是简单的排列组合，做左上角走到右下角，需要x次向右，y次像左走。所有的可能就是

,所以就转化为求阶乘的问题。因为x，y不超过十，最多就是20的阶乘，用long long int 足矣


	#include <iostream>



	using namespace std;



	





	long long int factorial(int m);



	int main(int argc, const char * argv[])



	{



	    int x,y;



	    cin>>x>>y;



	    long long int ways;



	    ways=factorial(x+y)/(factorial(x)*factorial(y));



	    cout<<ways;



	}



	long long int factorial(int m)



	{



	    long long int total=1;



	    int i=1;



	    for(;i<=m;i++)



	    {



	        total=total*i;



	    }



	    return total;



	}

发表于 2017-12-26 17:06:51 回复(0)

JavaScript

Orange。

while(line = readline()){
    var lines = line.split(' ');
    var a = parseInt(lines[0]),
        b = parseInt(lines[1]);
	function cellCount(x,y){
        var arr =[];
        //每个格点初始化为1
        for(var i=0; i<=x;i++){
            arr[i]=[];
            for(var j=0; j<=y;j++){
                arr[i][j] = 1;
            }
        }
        //每个格点的值是其左边和上边格点值的和
        for(var i=1;i<=x;i++){
            for(var j=1;j<=y;j++){
                arr[i][j] = arr[i-1][j] + arr[i][j-1];
            }
        }
        return arr[x][y];
    }
    print(cellCount(a,b));
}

发表于 2017-08-08 15:20:02 回复(3)

谁动了我的橘子

两个思路，一种动态规划，一种是递归，其实原理都是一样的。都是通过状态转移方程找到边界条件来求解。

可以看出网格中的到达网格中的任意一点的状态方程为： d(m,n)=d(m-1,n)+d(m,n-1)

也就是到达相邻的左节点和上节点的所有路线的和

边界条件：到达所有处于第一行跟第一列的所有的点的路线都只有一条。

知道了状态方程跟边界条件，那么我们就可以使用动态规划来解决了；

这里附上两个解法，第一个是动态规划，第二个是递归

import java.util.*;
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(dpHandle(init(m, n),m, n));
      //递归
      //System.out.println(recursiveHandle(init(m, n), m, n));
    }
  }
  public static int dpHandle( int[][] a ,int m, int n) {
    for (int i = 1; i < a.length; i++) {
      for (int j = 1; j < a[i].length; j++) {
        a[i][j] = a[i - 1][j] + a[i][j - 1];
      }
    }
    return a[m][n];
  }
  public static int[][] init(int m, int n) {
    int[][] a = new int[m + 1][n + 1];
    for (int i = 0; i < a[0].length; i++) {
      a[0][i] = 1;
    }
    for (int i = 0; i < a.length; i++) {
      a[i][0] = 1;
    }
    return a;
  }
  public static int recursiveHandle(int[][] a, int m, int n) {
    if (m == 0 && n == 0) {
      return 0;
    }
    if (m == 0 || n == 0) {
      return 1;
    }
    return recursiveHandle(a, m - 1, n) + recursiveHandle(a, m, n - 1);
  }
}

发表于 2018-08-16 22:06:55 回复(0)

CestLamour

解题思路：Nx1的网格以及 1xN的网格都遵循起点到终点的方法数为：N+1，其他点等于“肩上”两个网格的和，所有算法采用递归实现
图片说明

import sys
net = sys.stdin.readline().split()
x = int(net[0])
y = int(net[1])
def rec(x,y):
    if(x==1)or(y==1):
        return x+y
    else:
        return rec(x-1,y)+rec(x,y-1)
print(rec(x,y))

发表于 2018-07-31 14:30:27 回复(0)

欢聚内推小哥

我觉得一维dp数组就可以搞定了，第一次在排行榜暂时取第一。。。

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int x = Integer.parseInt(s[0]);
        int y = Integer.parseInt(s[1]);
        int[] dp=new int[y+1];
        Arrays.fill(dp,1);
        for(int i=1;i<=x;i++)
            for(int j=1;j<=y;j++)
                dp[j]+=dp[j-1];
        System.out.print(dp[y]);
    }

发表于 2018-04-28 22:27:23 回复(2)

小渣渣渣渣渣渣

l=(input().split())
x,y=int(l[0])+1,int(l[1])+1
l=[0]*x
l[0]=1
for p in range(y):
    for i in range(1,x):
        l[i]+=l[i-1]
print(l[-1])

//

每一个位置只能从左边或上面到达，方法数等于这两个位置方法数之和。

可以生成x*y的表，一个一个打出来。

空间压缩：只和左边和上面位置有关，可以压缩到min(x,y)

py大法好

发表于 2018-04-04 22:06:33 回复(0)

OutOfBoundsException

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt(), n = scan.nextInt();
        //排列组合 m+n步选取m步
        long a = 1, b = 1, c = 1;
        for (int i = 1; i <= m+n; i++) a *= i;
        for (int i = 1; i <= m; i++) b *= i;
        for (int i = 1; i <= n; i++) c *= i;
        System.out.println(a/(b*c));
    }
}

编辑于 2018-01-25 15:30:23 回复(0)

pein531

最简单的动态规划思路，dp[i][j]表示从左上角到位置(i, j)一共有多少种走法，而每个位置可能从上面和左边两个方向到达，所以得到状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]。但本题需要注意：是在网格点上走，所以一共有(x+1)*(y+1)个位置，而不是x*y个位置。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        // 初始化边界
        int[][] dp = new int[x + 1][y + 1];
        for(int i = 0; i <= x; i++)
            dp[i][0] = 1;
        for(int i = 0; i <= y; i++)
            dp[0][i] = 1;
        // 动态规划
        for(int i = 1; i <= x; i++){
            for(int j = 1; j <= y; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];    // 可能从上面，也可能从左边过来
        }
        System.out.println(dp[x][y]);
    }
}

编辑于 2021-02-02 12:56:25 回复(0)

C/C++

Debug丶

#include <iostream>
using namespace std;
int main()
{
    int nRows, nCols;
    while (cin >> nRows >> nCols)
    {
        if (nRows < 1 || nRows > 10 || nCols < 1 || nCols > 10)
        {
            cout << "0" << endl;
            continue;
        }
        int* pDP = new int[nRows + 1];
        for (int i = 0; i <= nCols; ++i)
            pDP[i] = 1;
        
        for (int i = 1; i <= nRows; ++i)
            for (int j = 1; j <= nCols; ++j)
                pDP[j] = pDP[j - 1] + pDP[j];
        
        cout << pDP[nCols] << endl;
        
        delete pDP;
    }
}

发表于 2019-08-19 13:54:53 回复(0)

C/C++

JoeWw

//注意原点是（1,1），若原点是（0,0），由于一秒走一格，若走到（x,y）,恰好横纵坐标的和就等于从（0,0）到(x,y)的最短时间。所以此题转化为求输入的对应x,y和的最小值，又因为原点是（1,1）最后减去2就ok。

#include <iostream>

using namespace std;

int max(int* x,int*y,int n) //函数功能：求对应x,y和的最小值

{

int temp=x[0]+y[0];

for(int i=0;i<n;i++)
if(temp>x[i]+y[i])
temp=x[i]+y[i];
return temp;

}

int main()
{
int n;
cin>>n;
if(n>1000)
return 0; //判断输入的n是否超过1000
int x[n],y[n];
for(int i=0;i<n;i++)
{
cin>>x[i];
}
for(int i=0;i<n;i++)
{
cin>>y[i];
}
cout<< max(x,y,n)-2; //由于原点是（1,1）减，最后max减去2。
return 0;
}

编辑于 2018-12-25 12:54:49 回复(0)

芒🍋

Python解答：

from sys import stdin

alist = []
line = stdin.readline().split()

for each in line:
if each != '':
alist.append(int(each))

cols = alist[0] + 1
rows = alist[1] + 1

def steps(cols, rows):
if cols == 1:
return 1
elif rows == 1:
return 1
else:
return steps(cols-1,rows) + steps(cols,rows-1)

print(steps(cols,rows))

发表于 2018-09-19 14:12:26 回复(0)

GYshadows

递归即可解决该问题，好好的学习递归真的很有用，哈哈，共勉
import java.util.Scanner;  public class root { public static void main(String[] args){
    Scanner input = new Scanner(System.in);  while (input.hasNextInt()){  int disX = input.nextInt();  int disY = input.nextInt();  System.out.println(road(0,0, disX,disY)); }
} public static int road(int x, int y, int disX, int disY){ int result = 0;  if (x <= disX && y <= disY){ if (x == disX && y == disY){ return 1;  }else { //向下走  result = result + road(x + 1, y, disX, disY);  //向右走  result = result + road(x , y + 1, disX, disY);  } return result;  }else { return 0;  }
}
}