首页 > 试题广场 >

方格走法

[编程题]方格走法

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

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

输入描述:

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

输出描述:

输出一行，表示走法的数目

示例1

输入

3 2

输出

算法知识视频讲解

超越姐姐保佑我i

题意不太明确，注意只能走格点，你画个网格就知道了。

所以 3 * 2 的网格，实际上格点数却是 4 * 3 。

dp解法

import java.util.*;
public class Main {
    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 ++) {
            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]);
    }
}

或者直接计算 C(n + m, n)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        int res = 1;
        for(int i = 1; i <= n; i ++) {
            res = res * (m + i) / i;
        }

        System.out.println(res);
    }
}

编辑于 2019-08-14 23:55:38 回复(2)

pjvs1478

因为只能向右走和向下，所以无论怎么走，向右的总距离和向下总距离都只能是x和y（即网格大小，曼哈顿距离不变），可以转换成排列组合问题，假设用0代表向右，1代表向左，题目转化成用x个0和Y个1能组成多少个不同的数，由排列组合公式可知，组合数应当是：

def cal_couple(num,i):
    sum = 1
    dvi_sum = 1
    for i in range(i):
        sum = sum*(num-i)
        dvi_sum = dvi_sum * (i+1)
    return (sum/dvi_sum)
if __name__ == '__main__':
    x,y = list(map(int,input().split()))
    print('%d' %(cal_couple(x+y,x)))

PS:python学得不好，见谅

发表于 2019-07-16 15:40:58 回复(1)

lentolove

就是一个排列组个问题 $C_{x+y}^x$ 一共要走 $x+y$ 步，哪 $x$ 步向右下走
注意阶乘溢出就行
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution15_方格走法 {

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String[] split = bf.readLine().split(" ");
    int x = Integer.parseInt(split[0]);
    int y = Integer.parseInt(split[1]);
    long a = 1,b = 1;
    int sum = x + y;
    int min = Math.min(x,y);
    for (int i = 1; i <= min; i++) {
        a *= i;
        b *= sum;
        sum--;
    }
    System.out.println(b / a);
}

}

编辑于 2019-08-16 19:09:33 回复(0)

Java

谁的电脑

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int a = x + y;
        int b = (x <= y) ? x : y;
        long denominator = 1, numerator = 1;
        for (int i = 1; i <= b; i++, a--) {
            denominator *= i;   // 1*2*3...
            numerator *= a;     // 10*9*8...
        }
        // (10*9*8*...)/(1*2*3*...)
        System.out.println(numerator / denominator);
    }
}

编辑于 2019-07-03 15:31:44 回复(0)

包子山

//排列组合
#include <iostream>
using namespace std;
int main()
{
    int x ,y;
    cin >> x  >> y;
    long long int  m = 1,n =1;
    for(int i = 1;i<=y;i++)
    {
        m *= (x+i);
        n *= i;
    }
    cout << m/n << endl;
    return 0;
}

发表于 2019-11-01 18:04:26 回复(0)

呃。。。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int y = in.nextInt();
        getKind(x,y,0,0);
        System.out.println(count);
    }
    
    private static int count = 0;
    
    private static void getKind(int rows,int cols,int r,int c){
        if (r == rows && c == cols){
            count++;
            return;
        }
        //向下走
        if (r+1<=rows)
            getKind(rows,cols,r+1,c);
        //向右走
        if (c+1<=cols)
            getKind(rows,cols,r,c+1);
    }
}

发表于 2019-08-13 15:31:59 回复(0)

C++

勇敢牛牛，不怕困难！

#include <iostream>
#include <vector>

using namespace std;

// DP 做法
int main(const int argc, const char** argv) {
  int m, n;
  cin >> m >> n;
  vector<vector<int>> grid(m + 1, vector<int>(n + 1, 1));
  for (int y = 1; y <= m; ++y)
    for (int x = 1; x <= n; ++x)
      grid[y][x] = grid[y - 1][x] + grid[y][x - 1];
  
  cout << grid[m][n];
  return 0;
}

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


int depth_first_search_with_memorization_algorithm(int* dp,
                                                    const int m,
                                                    const int n,
                                                    int x,
                                                    int y) {
  
  if (x == n || y == m)         return 0; // out of the boundary
  if (dp[y * n + x] >= 0)       return dp[y * n + x];     // 防止重复求解子问题
  if (x == n - 1 && y == m - 1) return dp[y * n + x] = 1; // reach to the goal
  
  int count = 0;
  count += depth_first_search_with_memorization_algorithm(dp, m, n, x + 1, y); // right 
  count += depth_first_search_with_memorization_algorithm(dp, m, n, x, y + 1); // down
  return dp[y * n + x] = count;
}


int main(const int argc, const char** const argv) {
  int m, n;
  fscanf(stdin, "%d %d", &m, &n);
  ++m, ++n;
  
  int dp[m][n];
  memset(dp, -1, sizeof dp);
  
  fprintf(stdout, "%d\n",
          depth_first_search_with_memorization_algorithm(dp, m, n, 0, 0));
  return 0;
}

发表于 2021-08-08 19:18:13 回复(0)

Java

lmz9509

/*
动态规划：dp[i][j]表示位于网格行列为i，j的时候所有的走法数目
dp[i][j] = dp[i][j-1] + dp[i-1][j]
当只有一行n列时只有一种走法，只有n行一列时只有一种走法
*/
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int x = input.nextInt();
        int y = input.nextInt();
        int[][] dp = new int[x+1][y+1];
        //动态规划
        for(int i = 0;i<x+1;i++){
            for(int j = 0;j<y+1;j++){
                if(i==0||j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }
            }
        }
        //结果
        System.out.println(dp[x][y]);
    }
}

发表于 2020-04-21 13:32:12 回复(0)

Java

LHC0512

import java.util.Scanner;

public class Main {

    static  int count =0;
    static  int x;
    static  int y;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        x=scanner.nextInt();
        y=scanner.nextInt();
        dfs(0,0);
        System.out.println(count);
    }
    
    private static void dfs(int currentX,int currentY){
        if (currentX>x||currentY>y)
            return;
        if (currentX==x&&currentY==y){
            count++;
            return;
        }else {
            dfs(currentX+1,currentY);
            dfs(currentX,currentY+1);
        }
    }
}

解法二：使用记忆化搜索

    static  int x;
    static  int y;
    static  int[][] arr;
    static int dfs(int currentX,int currentY){
        if (currentX>x||currentY>y)
            return 0;
        else  if (currentX==x&&currentY==y)
            return 1;
        else if (arr[currentX][currentY]!=0)
            return arr[currentX][currentY];
        else {
            arr [currentX][currentY]= dfs(currentX+1,currentY)+ dfs(currentX,currentY+1);
            return arr[currentX][currentY];
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        x=scanner.nextInt();
        y=scanner.nextInt();
        arr =new int[x+1][y+1];
        System.out.println(dfs(0,0));
    }

编辑于 2020-02-29 15:27:06 回复(0)

远方的蔚蓝

/*
利用递归来解决这个问题
我们从最终点出发往前递推x-1或者y-1
当有一个坐标变成0后说明有了一条道
而均不为0时继续-1的操作
*/
#include <stdio.h>
int x,y,count=0;
void way(int n,int m){
    if(n*m == 0){
        count ++;
        return;
    }
    way(n-1,m);
    way(n,m-1);
}
int main(){
    scanf("%d %d", &x, &y);
    way(x,y);
    printf("%d",count);
    return 0;
}

编辑于 2020-02-21 21:25:52 回复(0)

dragonlogin

#include<bits/stdc++.h>
using namespace std;
int main() {
	int m, n;
	cin >> m >> n;
	// 0,0 -> m, n
	vector<vector<int>> f(m+1, vector<int>(n+1,0));
	f[0][0] = 1;
	for (int i=0; i<=m; ++i) {
		for (int j=0; j<=n; ++j) {
			if (i-1 >= 0) {
				f[i][j] += f[i-1][j];
			}
			if (j-1 >= 0) {
				f[i][j] += f[i][j-1];
			}
		}
	}	
	cout << f[m][n] << endl;
	return 0;
}

编辑于 2019-10-19 14:59:34 回复(0)

C/C++

Andrew_Y

本题是很直观的动态规划题目，构造一个二维数组对应我们坐标右下方正增长的网格。
以f(x,y)为到(x,y)点的方法数，则f(x,y)=f(x-1,y)+f(x,y-1) x>1,y>1
f(x,y)=f(x-1,y) x>1,y==0
f(x,y)=f(x,y-1) x==0,y>1
初始值f(1,0)=1. f(0,1)=1

#include<iostream>
#include<vector>
using namespace std;
//动态规划
int main()
{
    int x,y;
    cin>>x>>y;
    //这里是因为如果我们的网格是x行y列，那么我们的对应的网点数为x+1行y+1列。
    x++;
    y++;
    vector<vector<int> > tmp(x);
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            tmp[i].push_back(0);
        }
    }
    //初始值
    tmp[1][0]=1;
    tmp[0][1]=1;
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            if(i==0&&j>1)
            {
                tmp[i][j]=tmp[i][j-1];
            }
            if(i>1&&j==0)
            {
                tmp[i][j]=tmp[i-1][j];
            }
            if(i>=1&&j>=1)
            {
                tmp[i][j]=tmp[i-1][j]+tmp[i][j-1];
            }
        }
    }
    //最后输出整个网点数组的右下角值即可
    cout<<tmp[x-1][y-1];
}

发表于 2019-10-14 17:26:15 回复(0)

北雷北雷

递归吧简单粗暴

#include <iostream>
using namespace std;
int rows,columns;

int dp(int x, int y) {
    if (x < rows&&y < columns) {
        return dp(x + 1, y) + dp(x, y + 1);
    }
    else return 1;
}

int main() {
    cin >> rows >> columns;
    cout << dp(0,0);
    system("pause");
    return 0;
}

发表于 2019-07-18 17:00:40 回复(1)

Python

ElonB

""""
考虑动态规划
设dp[x][y]为x*y的网格，每次只能向两个方向，有以下规律：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
边界条件为 dp[i][j]=1，(当i=0或j=0)
"""
if __name__ == "__main__":
    x, y = map(int, input().strip().split())
    dp = [[1] * (y + 1) for _ in range(x + 1)]
    for i in range(1, x + 1):
        for j in range(1, y + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[x][y])

编辑于 2019-07-11 22:43:03 回复(0)

C/C++

nbgao


	
	
		#include <bits/stdc++.h>
	

	
		using namespace std;
	

	
		int main(){
	

	
		int x, y;
	

	
		int dp[11][11] = {0};
	

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

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

	
		if(i==0 && j==0)
	

	
		dp[i][j] = 1;
	

	
		else if(i==0)
	

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

	
		else if(j==0)
	

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

	
		else
	

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

	
		}
	

	
		}
	

	
		// for(int i=1;i<=10;i++)
	

	
		//     for(int j=1;j<=10;j++)
	

	
		//     {
	

	
		//         if(j==10)
	

	
		//             cout<<dp[i][j]<<endl;
	

	
		//         else
	

	
		//             cout<<dp[i][j]<<" "; 
	

	
		//     }
	

	
		while(cin>>x>>y){
	

	
		cout<<dp[x][y]<<endl;
	

	
		}
	

	
		return 0;
	

	
		}

发表于 2019-07-06 20:04:31 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var x,y int
    fmt.Scan(&x,&y)
    mat:=make([][]int,x+1)
    for i,_:=range mat{
        mat[i]=make([]int,y+1)
    }
    for i:=0;i<=y;i++{
        mat[0][i]=1
    }
    for i:=0;i<=x;i++{
        mat[i][0]=1
    }
    for i:=1;i<=x;i++{
        for j:=1;j<=y;j++{
            mat[i][j]=mat[i-1][j]+mat[i][j-1]
        }
    }
    // fmt.Printf("%v\n",mat)
    fmt.Print(mat[x][y])
}

发表于 2023-03-18 22:08:38 回复(0)

louis_ncu

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int x = 0, y = 0;
    cin >> x >> y;
    vector<vector<int>> vec0;
        //坑点：路径为网格点而不是网格，所以要加1
    vector<int> vec1(y+1, 0);
    for (int i = 0; i <= x; i++) {
        vec0.push_back(vec1);
    }
    for (int i = 0; i <= x; i++) {
        vec0[i][0] = 1;
    }
    for (int j = 0; j <= y; j++) {
        vec0[0][j] = 1;
    }
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            vec0[i][j] = vec0[i - 1][j] + vec0[i][j - 1];
        }
    }
    cout << vec0[x][y] << endl;
    return 0;
}

编辑于 2020-04-28 23:55:27 回复(0)

C/C++

牛客961935183号

#include<bits/stdc++.h>
using namespace std;
int step(int x,int y){ if(x==0 || y==0) return 1;
    return step(x-1,y)+step(x,y-1); }
int main(){
    int i,j;
    cin>>i>>j;
    cout<<step(i,j);
}

发表于 2020-04-27 10:06:02 回复(1)

良17

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[][] dp = new int[x+1][y+1];
        dp[0][0] = 0;
        for(int i = 1;i < x+1;i++){
            dp[i][0] = 1;
        }
        for(int j = 1;j < y+1;j++){
            dp[0][j] = 1;
        }
        for(int i = 1;i < x+1;i++){
            for(int j = 1;j < y+1;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        System.out.println(dp[x][y]);
    }
}

发表于 2020-02-25 20:17:39 回复(0)

WMYW

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int x,y;
    cin>>x>>y;
    int(*p)[11]=new int[x+1][11];
  //  vector<vector<int>> v(x+1);
 //   for(int i=0;i<v.size();i++)
 //       v[i].resize(y+1);
    for(int i=0;i<y+1;i++)
        p[0][i]=1;
    for(int i=0;i<x+1;i++)
        p[i][0]=1;
    for(int i=1;i<x+1;i++)
    {
        for(int j=1;j<y+1;j++)
        {
            p[i][j]=p[i-1][j]+p[i][j-1];
        }
    }
    cout<<p[x][y];
}

发表于 2020-02-14 09:44:28 回复(0)