直接使用数学方法路径数 | #求路径#

题目: NC34 求路径

如图,把旧起点转换成新起点,4×3网格变为3×2网格,由数学知识易知: 答案为:$\left(\genfrac{}{}{0px}{}{2}{3+2}\right)\backslash tbinom\{2\}\{3+2\}$即$\left(\genfrac{}{}{0px}{}{2}{5}\right)\backslash tbinom\{2\}\{5\}$ 即:(5!/(5-2)!) / (2!),由此,如下计算:

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
        public int uniquePaths (int m, int n) {
        // write code here
        int m1=m+n-2;
        int n1=Math.min(m,n)-1;
        long q1=1;
        long q2=1;
        for(int i=0;i<n1;i++){
            q1*=m1--;
        }
        for(int i=1;i<=n1;i++){
            q2*=i;
        }
        return (int)(q1/q2);
    }
}

主要注意点: q1如果是int型,可能超出int范围,故用long; 但是该方法确实规避了考察点:动态规划!

运行结果: