тема
Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на изображении ниже).
Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже).
В. Сколько всего существует различных путей?
Например, изображение выше представляет собой сетку 7 x 3. Сколько существует возможных путей?
Объяснение: значения m и n не превосходят 100.
Пример 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
Пример 2:
输入: m = 7, n = 3
输出: 28
отвечать
Когда я узнаю название этого вопроса, я думаю, что первая реакция каждого состоит в том, что это должен быть рекурсивный вопрос, потому что мы можем преобразовать его в подзадачу, но насилие определенно истечет по времени, поэтому нет необходимости пытаться. Фактически, рекурсивный метод в этом вопросе состоит в том, чтобы продолжать попытки сверху вниз, Если мы сможем вспомнить предыдущие результаты, это поможет нам на следующем шаге, поэтому мы подумали о методе DP. Число в сетке представляет текущий метод.
-
начальное состояние
-
В настоящее время это состояние относится только к левой и верхней сеткам.
-
Решить последовательно
Таким образом, мы можем получить уравнение перехода состояний:
ways[i][j] = ways[i-1][j] + ways[i][j-1];
Java-код
public class Solution {
public int uniquePaths(int m, int n) {
int[][] ways = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) ways[i][j] = 1;
else ways[i][j] = ways[i-1][j] + ways[i][j-1];
}
}
return ways[m-1][n-1];
}
}
оптимизация
Когда мы решаем на рисунке 3 выше, мы решаем его построчно.На самом деле нам нужно только записать, что в текущей строке есть несколько путей, когда мы переходим к (i, j), если мы переходим к (i, j m-1) Когда , просто замените путь соответствующего столбца в этой строке, чтобы запрограммировать уравнение перехода состояния: разрешение [j] = разрешение [j] + разрешение [j-1]
class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[] res = new int[n];
res[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
res[j] += res[j - 1];
System.out.println("i=" + i + "_" + "j=" + j + ":" + Arrays.toString(res));
}
}
return res[n - 1];
}
}
Некоторые студенты могут все еще не понять, я напечатал некоторую информацию в коде, чтобы облегчить понимание:
i=0_j=1:[1, 1, 0, 0, 0, 0, 0]
i=0_j=2:[1, 1, 1, 0, 0, 0, 0]
i=0_j=3:[1, 1, 1, 1, 0, 0, 0]
i=0_j=4:[1, 1, 1, 1, 1, 0, 0]
i=0_j=5:[1, 1, 1, 1, 1, 1, 0]
i=0_j=6:[1, 1, 1, 1, 1, 1, 1] //只记录到这一行的信息
i=1_j=1:[1, 2, 1, 1, 1, 1, 1]
i=1_j=2:[1, 2, 3, 1, 1, 1, 1]
i=1_j=3:[1, 2, 3, 4, 1, 1, 1]
i=1_j=4:[1, 2, 3, 4, 5, 1, 1]
i=1_j=5:[1, 2, 3, 4, 5, 6, 1]
i=1_j=6:[1, 2, 3, 4, 5, 6, 7] //只记录到这一行的信息
i=2_j=1:[1, 3, 3, 4, 5, 6, 7]
i=2_j=2:[1, 3, 6, 4, 5, 6, 7]
i=2_j=3:[1, 3, 6, 10, 5, 6, 7]
i=2_j=4:[1, 3, 6, 10, 15, 6, 7]
i=2_j=5:[1, 3, 6, 10, 15, 21, 7]
i=2_j=6:[1, 3, 6, 10, 15, 21, 28] //只记录到这一行的信息
i=3_j=1:[1, 4, 6, 10, 15, 21, 28]
i=3_j=2:[1, 4, 10, 10, 15, 21, 28]
i=3_j=3:[1, 4, 10, 20, 15, 21, 28]
i=3_j=4:[1, 4, 10, 20, 35, 21, 28]
i=3_j=5:[1, 4, 10, 20, 35, 56, 28]
i=3_j=6:[1, 4, 10, 20, 35, 56, 84] //只记录到这一行的信息
Math
На самом деле этот вопрос можно решить путем перестановки и комбинации. Собственно, этот метод и пришел мне в голову в первую очередь. Взяв смоделированный пример [4, 7], каждый путь:
- Вправо должно быть 6 шагов;
- Влево определенно 3 шага; Проблема в следующем: c(9,3) = (9 * 8 * 7) / (1 * 2 * 3) = 84
Формула комбинированного числа: c(m,n) = m! / (n! * (m - n)!)
Java-код
Java, непосредственно применяющая формулу, выйдет за границы Я использую long для хранения следующих результатов:
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
13!=6227020800
14!=87178291200
15!=1307674368000
16!=20922789888000
17!=355687428096000
18!=6402373705728000
19!=121645100408832000
20!=2432902008176640000
21!=-4249290049419214848
22!=-1250660718674968576
23!=8128291617894825984
24!=-7835185981329244160
Нужно немного упростить, процесс упрощения — мой второй шаг в решении c(9,3).
class Solution {
public int uniquePaths(int m, int n) {
double dom = 1;
double dedom = 1;
int small = m < n ? m - 1 : n - 1;
int big = m < n ? n - 1 : m - 1;
for (int i = 1; i <= small; i++) {
dedom *= i;
dom *= small + big + 1 - i;
}
return (int) (dom / dedom);
}
}
код питона
Код Python более жестокий, и выполняется одна строка кода:
class Solution:
def uniquePaths(self, m, n):
return int(math.factorial(m + n - 2) / math.factorial(m -1) / math.factorial(n-1))
Вставьте код версии DP
class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
if m <= 0 or n <= 0:
return 0
res = [0 for _ in range(0, n)]
res[0] = 1
for i in range(0, m):
for j in range(1, n):
res[j] += res[j-1]
return res[n-1]