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

一、动态规划法：

import java.util.*;

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];//起点到i，有多少种走法
        //状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 || j == 1) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}

二、深搜法（TLE）

int fm;
    int fn;
    int[][] path;
    boolean[][] isVisted;
    int count = 0;

    //输入起点坐标，dfs深度搜索返回路径值
    void dfs(int sx, int sy) {
        if (sx == fm && sy == fn) {
            count++;
            return;
        }
        if (sx > fm || sy > fn) {
            return;
        }
        if (sx < fm && !isVisted[sx][sy]) {
            isVisted[sx][sy] = true;
            dfs(sx + 1, sy);
            isVisted[sx][sy] = false;
        }
        if (sy < fn && !isVisted[sx][sy]) {
            isVisted[sx][sy] = true;
            dfs(sx, sy + 1);
            isVisted[sx][sy] = false;
        }
    }

    //从(0, 0)到(m-1, n-1)有多少种走法，每次只能向下或向右移动
    public int uniquePaths(int m, int n) {
        fm = m - 1;
        fn = n - 1;
        path = new int[m][n];//路径数组
        isVisted = new boolean[m][n];//访问数组
        dfs(0, 0);
        return count;
    }

三、递归法

public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }