首页 > 试题广场 >

方格走法

[编程题]方格走法
  • 热度指数：2688 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有一个X*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。


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


输出描述:
输出一行，表示走法的数目
示例1

输入

3 2

输出

10
算法知识视频讲解
添加回答
十年单身换一个字节SP头像 十年单身换一个字节SP
这个是一个很简单的动态规划，4399笔试的时候也考了这个题目。就是先把边界设为1，然后直接每次递推，递推公式为：a[i][j]=a[i+1][j]+a[i+1][j]，但是这个个题目有一个坑，他输入1,1的时候输出为2，那就意味着，长宽都要加1.具体代码如下： 
#include<bits/stdc++.h>
usingnamespacestd;
inta[11][11]={0};
intmain(){
    intm,n;
    cin>>m>>n;
    if(m==0||n==0){
        cout<<1<<endl;
        return0;
    }else{
        for(inti=0;i<=m;i++)a[i][n]=1;
        for(inti=0;i<=n;i++)a[m][i]=1;
        for(inti=m-1;i>=0;i--){
            for(intj=n-1;j>=0;j--){
                a[i][j]=a[i][j+1]+a[i+1][j];
            }
        }
        cout<<a[0][0]<<endl;
    }
    return0;
}

发表于 2019-03-27 20:31:02 回复(3)
更多回答
C/C++
欢欢喜喜鸭老板头像 欢欢喜喜鸭老板
#include<stdio.h>

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int s[n+1][m+1];
    for(int i=0;i<=n;i++)
        s[i][0] = 1;
    for(int j=0;j<=m;j++)
        s[0][j] = 1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
                s[i][j] = s[i-1][j] + s[i][j-1];
        }
    }
    printf("%d",s[n][m]);
    return 0;
}
发表于 2019-08-23 11:25:46 回复(0)
Java
Cheng.Y头像 Cheng.Y 
动态规划
import java.util.Scanner;
public class Main {
    public static int ways(int x, int y){
        if(x==1 || y==1){
            return x*y+1;
        }
        return ways(x-1,y)+ways(x,y-1);

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int x = in.nextInt();
            int y = in.nextInt();
            System.out.println(ways(x,y));
        }

    }
}
编辑于 2019-04-03 15:46:32 回复(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;
}

发表于 2021-08-08 18:53:13 回复(0)
初心者托奇头像 初心者托奇 
from functools import reduce
def jiecheng(x):
    return reduce(lambda y,z:y * z,range(1,1 + x))
a = list(map(int,input().split()))
print(int(jiecheng(sum(a)) / jiecheng(a[0]) / jiecheng(a[1])))

发表于 2020-03-17 21:37:40 回复(0)
JavaScript
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:蘑菇街🍄-方格走法（DP）
leetcode 64 不同路径 
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        let arr = inArr[0].split(' ').map(e=>+e)
        let x = arr[0]
        let y = arr[1]
        let res = uniquePaths(x, y)
        console.log(res)
        }
})
var uniquePaths = function(x, y) {
    let dp = []
    for(let i=0; i<=x; i++)
    {
        dp[i]=[]
    }
    for(let i=0; i<=x; i++)
    {
        for(let j=0; j<=y; j++)
        {
            if(i==0 || j==0)
                dp[i][j]=1
            else
                dp[i][j]=dp[i][j-1]+dp[i-1][j]
        }
    }
    return dp[x][y]
};

发表于 2020-02-26 23:37:29 回复(0)
小蝌蚪666头像 小蝌蚪666 
#include <iostream>
using namespace std;
int f(int n, int k){
    int sum = 1, i = 1;
    if(k * 2 > n)
        k = n-k;
    while(i <= k){
        sum *= n;
        sum /= i;
        ++i;
        --n;
    }
    return sum;
}
int main(void){
    int x, y;
    cin>>x>>y;
    cout<<f(x+y, y)<<endl;
    return 0;
}
X*Y方格的走访总数为组合数，也不用dp建立表格或者递归，注意计算组合数时分母从1开始递增而不是从x开始递减
发表于 2019-08-26 17:42:07 回复(0)
Java
嘿嘿嘿嘿哒头像 嘿嘿嘿嘿哒 
import java.util.*;
public class Main {

/*  **用组合数，总共需要x+y步，挑x步走，或者挑y步走 
 */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x=sc.nextInt();
        long y=sc.nextInt();
        System.out.println(jc(x+y)/(jc(x)*jc(y)));

    }
    private static long jc(long n){//阶乘
        long sum=1;
        for (long i = 1; i <= n ; i++) {
           sum*=i;
        }
        return  sum;
    }
}

发表于 2019-08-14 11:56:24 回复(0)
Jurenly头像 Jurenly 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int x,y;
    cin>>x>>y;

    vector<vector<int>>dp(x+1,vector<int>(y+1,0));
   
    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-1][j]+dp[i][j-1];
            }
        }
    }
    cout<<dp[x][y]<<endl;
    return 0;
}

发表于 2019-08-06 09:57:11 回复(0)
C/C++
nbgao头像 nbgao
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int dp[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];
        }
    cout<<dp[n][m]<<endl;
    return 0;
}
发表于 2019-07-24 17:25:46 回复(0)
Python
ElonB头像 ElonB 
""""
动态规划，dp[x][y]表示所有走法的数目
到达x,y点的路径只有两条，从上边和从左边
dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
边界 dp[0][y] = dp[x][0] = 1
"""

if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    dp = [[1] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    print(dp[n][m])

发表于 2019-07-16 13:35:04 回复(0)
湮静安头像 湮静安
很常规的一道dp题，本题要注意的是它是在格点上走，而非格子上走 
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;

#define m 15
int main()
{     int x, y;     int i, j;     int dp[m][m];     cin >> x >> y;     for (i = 0; i <= x; i++)     {
               /*初始化dp数组的第1列为1*/         dp[i][0] = 1;         for (j = 1; j <= y; j++)         {
                        /*初始化dp数组的第一行为1，若不是第一行则左边格点的路线数加上上边格点的路线数*/             if(i==0)                 dp[0][j] = 1;             else             {                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];             }         }     }     cout << dp[x][y] << endl;     system("pause");     return 0;
}

发表于 2019-05-21 14:31:32 回复(0)
菜鸡🐔🐔头像 菜鸡🐔🐔 
import java.util.Scanner;
import java.lang.Integer;

public class Main {
    public static int resultCount (int x, int y) {
        if (x == 0 || y == 0) {
            return 1;
        }
        return resultCount(x-1, y) + resultCount(x, y-1);
    }
    public static void main(String [] args) {
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        String[] ss = str.split(" ");
        int x = Integer.parseInt(ss[0]);
        int y = Integer.parseInt(ss[1]);

        int result = resultCount(x,y);
        System.out.print(result);
    }
}

编辑于 2019-04-16 16:44:13 回复(0)
有如头像 有如 
import java.util.Scanner;

/**
 * 方格走法
 *
 * @author chensiqu
 * @since 2019/4/2 17:10
 */
public class GridWay {

    private static int count = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int x, y;
        x = scanner.nextInt();
        y = scanner.nextInt();
        // 递归解法
        core(x, y, 0, 0);
        System.out.println(count);

        // 动态规划数组，数组内数值为到这点的走法。
        int[][] ints = new int[x + 1][y + 1];
        // 初始化 第一行走法全为 1
        for (int i = 0; i < y + 1; i++) {
            ints[0][i] = 1;
        }
        // 初始化 第一列走法全为 1
        for (int i = 1; i < x + 1; i++) {
            ints[i][0] = 1;
        }
        // 从 ints[1][1]开始，这点的走法为上方的点加上左方的点走法相加。
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                ints[i][j] = ints[i - 1][j] + ints[i][j - 1];
            }
        }
        System.out.println(ints[x][y]);

    }

    /**
     * 递归深度优先遍历解法
     *
     * @param rows 行
     * @param cols 列
     * @param i    横坐标
     * @param j    纵坐标
     */
    private static void core(int rows, int cols,
                             int i, int j) {
        if (i > rows || j > cols) {
            return;
        }
        // 到达目标点，则 count++
        if ((i == rows) && (j == cols)) {
            count++;
            return;
        }
        // 深度优先遍历
        core(rows, cols, i + 1, j);
        core(rows, cols, i, j + 1);
    }
}

编辑于 2019-04-03 09:44:02 回复(0)
梦秋音头像 梦秋音
```
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();
        System.out.println(f(x,y));
    }
    
    public static int f(int x,int y) {
        if(x==1) return y+1;
        if(y==1) return x+1;
        return f(x-1,y)+f(x,y-1);
    }
}
```
发表于 2019-03-29 19:32:21 回复(0)
Go
小谷围做题家头像 小谷围做题家 
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.Print(mat[x][y])
}

发表于 2023-03-21 14:41:30 回复(0)
牛客577127890号头像 牛客577127890号
来个不用dp，不用递归的解法。
实际上就是，从（x+y）步中，选出y步向下走或者选出x步向右走。高中数学问题。 
import java.util.*;
public class Main{
    public static long jc(int n){
        long x=1;
        for(int i=1;i<=n;i++){
            x*=i;
        }
        return x;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int x=sc.nextInt();
            int y=sc.nextInt();
            System.out.println(jc(x+y)/(jc(x)*jc(y)));
        }
    }
}

发表于 2020-09-19 19:49:49 回复(0)
C/C++
牛客549207409号头像 牛客549207409号
#include<iostream>
#include<vector>
int main()
{
    int x,y;
    while(std::cin>>x>>y)
    {
        std::vector<std::vector<int>>dp(x+1,std::vector<int>(y+1,0));
        dp[0][0]=0;
        for(int i=1;i<=x;i++)dp[i][0]=1;
        for(int i=1;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];
        }
        std::cout<<dp[x][y]<<std::endl;
    }
    return 0;
}
发表于 2020-09-19 08:52:20 回复(0)
DearSummer头像 DearSummer
https://leetcode-cn.com/problems/unique-paths/solution/
leetcode62
编辑于 2020-09-14 15:19:43 回复(0)
Python
牛客239836399号头像 牛客239836399号 
s = input()
x = int(s.split()[0])
y = int(s.split()[1])
def foo(a, b):
    if a == 1 and b == 1:
        return 0
    if a == 1&nbs***bsp;b == 1:
        return 1
    return foo(a, b-1) + foo(a-1, b)
print(foo(x+1, y+1))
编辑于 2020-07-08 15:25:35 回复(0)
提交观点

问题信息

C++工程师 动态规划 测试工程师 2019 数学 蘑菇街 Java工程师
上传者：小小
难度：
41条回答 8062浏览

热门推荐

通过挑战的用户

查看代码

相关试题

方格走法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号