方格走法

[编程题]方格走法

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

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

输入描述:

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

输出描述:

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

示例1

输入

3 2

输出

算法知识视频讲解

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)

Java

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)

Java

Miracle1414

基础的动态规划题

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x=sc.nextInt()+1,y=sc.nextInt()+1;
        int[][] dp = new int[x+1][y+1];
        dp[1][0]=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.print(dp[x][y]);
    }
}

发表于 2019-04-02 17:21:17 回复(0)