不同路径

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

深度优先解法：

class Solution {
    private int[][] map;
    private int[][] book;
    private int ans;
    private int m;
    private int n;

    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        map = new int[m][n];
        book = new int[m][n];
        book[0][0] = 1;
        dfs(0,0);
        return ans;
    }

    /**
     * 0,1代表向下,1,0代表向右
     * @param index
     * @return
     */
    private int[] getNextStep(int index){
        int[][] step = new int[][]{{1,0},{0,1}};
        return step[index];
    }

    private void dfs(int x,int y){
        //判断当前是否是终点
        if(x == m-1 && y == n-1){
            ans += 1;
            return;
        }
        //没到终点，尝试下一步
        for(int i = 0;i<2;i++){
            int[] next = getNextStep(i);
            int nextX = x+next[0];
            int nextY = y+next[1];
            //判断是否越界已经是否已经走过
            if(nextX >= m || nextY >=n || nextX < 0 || nextY <0 || book[nextX][nextY] == 1)
                continue;
            //可以走，标记为走过
            book[nextX][nextY] = 1;
            dfs(nextX,nextY);
            //取消标记
            book[nextX][nextY] = 0;
        }
    }
}

广度优先解法：

class Solution {

    class Track{
        int x;
        int y;
        Track(int x,int y){
            this.x = x;
            this.y = y;
        }
    }

    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        int ans = 0;
        int[][] book = new int[m][n];
        List<Track> tracks = new ArrayList<>();
        tracks.add(new Track(0,0));
        int left = 0;
        int right = left;
        while(left <= right){
            Track track = tracks.get(left);
            //找出当前步的下一步（所有合法的下一步）
            for(int i=0;i<2;i++){
                int[] next = getNextStep(i);
                int nextX = track.x + next[0];
                int nextY = track.y + next[1];
                //判断是否过界以及是否走过
                if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n)
                    continue;
                //判断是否到达终点
                if (nextX == m-1 && nextY == n-1){
                    ans++;
                }else{
                    //标记已经走过
                    //没到终点
                    right++;
                    tracks.add(new Track(nextX,nextY));
                }
            }
            left++;
        }
        return ans;
    }

    /**
     * 0,1代表向下,1,0代表向右
     * @param index
     * @return
     */
    private int[] getNextStep(int index){
        int[][] step = new int[][]{{1,0},{0,1}};
        return step[index];
    }

}

动态规划解法

class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        int[][] book = new int[m][n];
        book[0][0] = 0;
        //先初始化上边一行
        for (int i = 1;i<n;i++){
            book[0][i] = 1;
        }
        //初始化最左边一行
        for (int i=1;i<m;i++){
            book[i][0] = 1;
        }
        for(int i = 1;i<n;i++){
            for (int j = 1;j<m;j++){
                book[j][i] = book[j-1][i] + book[j][i-1];
            }
        }
        return book[m-1][n-1];
    }
}