题解 | #不同路径的数目(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        // 算法核心思想：记忆化搜索

        // dp[i][j]表示当位置落在i,j上时，有几种走法可以到达m-1,n-1
        // 初始化-1
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }

        return process(m, n, 0, 0, dp);
    }

    public int process (int m, int n, int i, int j, int[][] dp) {
        // 递归出口
        if (i == m - 1 && j == n - 1) {
            dp[i][j] = 1;
            return dp[i][j];
        }

        // 递归分支
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        // 往下走
        int d = 0;
        if (i < m - 1) {
            // 不会越界，可以走
            if (dp[i + 1][j] == -1) {
                dp[i + 1][j] = process(m, n, i + 1, j, dp);
            }
            d = dp[i + 1][j];
        }
        // 往右走
        int r = 0;
        if (j < n - 1) {
            // 不会越界，可以走
            if (dp[i][j + 1] == -1) {
                dp[i][j + 1] = process(m, n, i, j + 1, dp);
            }
            r = dp[i][j + 1];
        }

        // 本位置的走法，等于向右走的走法 + 向下走的走法
        dp[i][j] = d + r;
        return dp[i][j];
    }
}