java - 有一个x*y网络，小团在此网格上从左上角走到右下角，只能走格点且只能往右走或往下走

Question

计算有多少种走法。给定正整数int x,int y,请返回小团的走法数目
输入一行，逗号隔开的正整数x,y取值范围〔1，10〕
输出包括一行，为走法数目

function main(parm_1,param_2,param_n){
    if(parm_1=parm_2){
        param_n = parm_1 = 1 ?2 :2+4^(parm_1-1);
    }
    if(parm_1=parm_2>1){
        param_n = 2+;
    }
    if(parm_1>parm_2){
        param_n = ;
    }
    if(parm_1<parm_2){
        param_n = ;
    }
    return param_n;
}

Answer 1

看下面的图

计算过程：

1. 把底边和右边的每个格子标记为1

2. 其余格子从右下角往右上角依次遍历

3. 每个格子的值是其右边和下边格子值的和

4. 遍历到右上角后求得最终结果

例如上图的结果为10。

这种解法依据的思路，由于每个格子只能向右或向下走，那么它的走法就由其右边格子的走法和下边格子的走法之和。而最下边和最右边的每个格子都只有唯一的走法。由此就能推导出其余格子的走法。

PS：这种方法需要遍历一遍，复杂度为O(n)。除了这种方法之外，也许还可以从数学的角度来找到通项公式，从而一次求得最终结果也说不定。