Nov 2, 2020 · 3 min read
Робот находится в левом верхнем углу, и может двигаться только вправо и вниз.
Сколько всего уникальных путей, которыми робот может добраться до правого нижнего угла?
Решение #
Робот начинает движение в левом верхнем углу, и в каждый момент времени может свернуть: вниз или направо. Разумеется, когда доходим до края поля — выходить за него нельзя. Идти назад так же нельзя, поэтому робот гарантированно окажется в точке финиша.
За счет того, что в каждый момент времени можно свернуть — получаем некое множество возможных путей. Именно их количество и нужно посчитать. Важно понимать, что речь не о количество шагов, а возможных вариантах добраться из одного угла в другой. Скажем, если робот будет идти до упора направо, а потом вниз — это ровно один вариант.
Первый вариант решения — обход в глубину. Я уже разбирал задачи на DFS, суть везде одна: есть дерево возможных вариантов обхода поля, надо посчитать количество веток от корня к листьям.
В данном случае, решать через DFS можно, но медленно. Чтобы найти количество веток придётся обойти все узлы дерева. Сколько там узлов? На каждом шаге есть два возможных варианта, т.е. каждый узел имеет двух деток. В итоге, сложность по времени O(2^(n * m)), где n и m размерности поля.
Какие ограничения в данной задаче? Вопрос, который надо задать интервьюеру в процессе обдумывания решения. Кидаться писать DFS, не выяснив этот момент — красный флаг.
Ограничения в условии — 1 <= m, n <= 100. Понятно, что в худшем случае 2 ^ (100 * 100) ни в какие ворота не лезут.
Конечно, можно легко перейти от DFS к варианту с мемоизацией, например, как в задаче про домино и тримино.
Чтобы не повторяться разберём классическое решение через динамическое программирование.
Суть метода в том, чтобы решить задач для тривиального базового случая, а после — продвигаться к решению задачи для n + 1, используя предыдущие результаты.
Так и поступим.
Обычно, в качество «той самой задачи, которую надо решать используя предыдущие результаты», выбирается ответ на вопрос в исходной задаче. В данном случае, заводим матрицу, каждый элемент которой отвечает на вопрос — сколько есть различных путей добраться в данную клетку?
Есть два возможных варианта оказаться в любой клетке — спуститься сверху или прийти слева. Соответственно, количество вариантов оказаться в данной клетке равно сумме вариантов оказаться сверху и слева, это и есть рекуррентное соотношение.
Соотношение есть, теперь надо подумать про базовый случай. Представим, что есть только один горизонтальный ряд. Сколько есть вариантов добраться от левого краю в любую клетку? Всего один. Потому что двигаться можно только впарво. Аналогично и для одного вертикального ряда, потому что двигаться можно только вниз.
Сложность данного решения — O(n * m), потому что надо просто заполнить матрицу соответствующего размера. Так же и по памяти.
На самом деле, использоваться будут только два ряда в каждый момент времени, поэтому всю матрицу хранить не обязательно. Для простоты я опускаю этот момент, а на интервью — это стандартный вариант развития вопроса, если остаётся время.
Теперь, когда решение есть, можно писать код.
/**
* @param {number} h
* @param {number} w
* @return {number}
*/
var uniquePaths = function(h, w) {
// каждый элемент матрицы отвечает на вопрос:
//«сколько есть возможных вариантов оказаться
// в данной клетке, следуя указанным правилам?»
const dp = new Array(h).fill(0).map(() => new Array(w));
// базовый случай:
// для вертикали и горизонтали
dp[0][0] = 1;
for (let x = 1; x < w; x++) {
dp[0][x] = 1;
}
for (let y = 1; y < h; y++) {
dp[y][0] = 1;
}
// заполняем матрицу ответов,
// постепенно приближаясь к ответу на задачу
// размера h x w, т.е. решению
for (let y = 1; y < h; y++) {
for (let x = 1; x < w; x++) {
dp[y][x] = dp[y - 1][x] + dp[y][x - 1];
}
}
// в правом нижнем углу — ответ исходной задачи
return dp[h - 1][w - 1];
};PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗
Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.