牛客网在线编程:网格走法数目

2018/03/06 16:11
阅读数 5

题目:

有一个X*Y的网格,小团要在此网格上从左上角到右下角,只能走格点且只能向右或向下走。请设计一个算法,计算小团有多少种走法。给定两个正整数int x,int y,请返回小团的走法数目。
输入描述:
输入包括一行,逗号隔开的两个正整数x和y,取值范围[1,10]。
输出描述:
输出包括一行,为走法的数目。
示例1
输入

3 2
输出

10

思路:

递归。只能走网格上的点。建立一个二维坐标轴,每个格子在遍历之前,必须经过它的左边或者上边的点。
即可找出递归公式f(x,y)=f(x-1,y)+f(x,y-1)
f(0,0)=1,f(0,1)=1,f(1,0)=1,f(1,1)=2,f(1,2)=3

 1 import java.util.*;
 2 public class Wanggezoufa {
 3     public static int step(int x,int y){
 4         if(x==0&&y==0) return 1;
 5         if(x==0||y==0) return 1;
 6         else return step(x-1,y)+step(x,y-1);
 7     }
 8     public static void main(String[] args) {
 9         // TODO Auto-generated method stub
10         Scanner sc = new Scanner(System.in);
11         int x = sc.nextInt();
12         int y = sc.nextInt();
13         System.out.println(Wanggezoufa.step(x,y));
14     }
15 
16 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部