方格走法

[编程题]方格走法

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

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

输入描述:

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

输出描述:

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

示例1

输入

3 2

输出

算法知识视频讲解

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)

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)