关于java:LeetCode062不同路径

43次阅读

共计 1070 个字符，预计需要花费 3 分钟才能阅读完成。

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

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

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

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：递归法

首先，通过剖析可知，达到任意一个单元格子的最初一步，能够从这个格子的右边过去，也能够从这个格子的上边过去，所以达到任意一个格子的步数是到它右边的步数加上到它下面格子的步数之和，所以能够用递归的办法求解，具体过程如下：

如果 m 等于 1 或者 n 等于 1，间接返回 1；

如果下面的条件不满足，则递归调用该办法求解uniquePaths(m - 1, n) + uniquePaths(m, n - 1)。

解法二：迭代法

首先记录第一行的格子的数字都是 1，而后因为第一列的值都是 1，而上面的每一行的 1 ~ n-1 列的值都能够依据以后行的右边的格子和上一行的下面的格子的值相加所得，所以通过迭代失去每一行的值，最初返回最初一行的最初一个值即为最终后果。

public class LeetCode_062 {
    /**
     * 递归
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths(int m, int n) {if (m == 1 || n == 1) {return 1;}
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }

    /**
     * 迭代
     *
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths1(int m, int n) {if (m == 1 || n == 1) {return 1;}
        int[] row = new int[n];
        for (int i = 0; i < n; i++) {row[i] = 1;
        }
        for (int i = 2; i <= m; i++) {for (int x = 1; x < row.length; x++) {row[x] = row[x - 1] + row[x];
            }
        }
        return row[n - 1];
    }

    public static void main(String[] args) {System.out.println(uniquePaths(51, 9));
        System.out.println(uniquePaths1(51, 9));
    }
}