题解 | #不同路径的数目(一),记忆化递归#

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        if(m == 0 || n == 0) return 0 ;
        int f[][] = new int[m][n] ;////f[i][j]表示从[i][j]到达终点的方式数
        return help(0 , 0 , m-1 , n-1 , f) ;
    }
    //从（x,y）到达（m1 , n1）的方式数
    public int help(int x , int y , int m1 , int n1 , int[][] f) {
        if(f[x][y] != 0) return f[x][y] ;
        if(x == m1 || y == n1) return 1 ;
        if(x > m1 || y > n1) return 0 ;
        f[x][y] = help(x+1 , y , m1 , n1 , f) + help(x , y+1 , m1 , n1 , f) ;
        return f[x][y] ;
    }
}