hot100-跳跃游戏

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

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

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

一开始最先想到的是深度优先加回溯，写完提交后发现超出时间限制，因为一旦mn变大，路径过于复杂。后来参考题目标签才意识到这个题目属于动态规划的范畴，使用动态规划也确实方便，d[i] [j] = d[i-1] [j]+d[i] [j-1] 最左边的一列和最上边的一行都是1，如此更新整个d[m] [n]即可。

后面发现空间复杂度较大，对空间进行优化，发现实际上更新时是使用一行一行的一次更新那么只开辟一个new int[n]即可，d[i] = d[i]+d[i-1]，这里d[i]在更新前实际上就是d[i] [j-1]。

//回溯的代码：

public static int uniquePaths(int m, int n) {
       res = 0;
       fun(m,n,1,1);
       return res;
}
public static void fun(int m,int n,int i,int j){
    if(i==m&&j==n){
        res++;
        return;
    }
    if(i==m)fun(m,n,i,j+1);
    else if(j==n)fun(m,n,i+1,j);
    else{
        fun(m,n,i,j+1);
        fun(m,n,i+1,j);
    }
}

//动态规划：

public static int uniquePaths2(int m, int n){
    int[][] d = new int[m][n];
    for (int i = 0; i < m; i++) {
        d[i][0] = 1;
    }
    for (int i = 0; i < n; i++) {
        d[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            d[i][j] = d[i][j-1]+d[i-1][j];
        }
    }
    return d[m-1][n-1];
}

//空间优化后的动态规划

public static int uniquePaths3(int m, int n){
    int[] d = new int[n];
    for (int i = 0; i < n; i++) {
        d[i] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(j == 0 ){
                d[j] = 1;

            }else{
                d[j] = d[j]+d[j-1];
            }

        }
    }
    return d[n-1];
}