170 похожих чатов

// В таблице из n строк и m столбцов клетки

заполнены цифрами от 0 до 9.
// Требуется найти такой путь из клетки (1,1) в клетку (n, m),
// чтобы сумма цифр в клетках, через которые он пролегает, была минимальной;
// из любой клетки ходить можно только вниз или вправо.
Может кто пояснить, насколько быстро будет работать алгоритм для решения такой задачки?
Дело в том, что я её вроде как решил, но для матрицы размером больше чем 13x13 решает довольно долго

11 ответов

29 просмотров

довольно долго это сколько?

та конечно можно

Иван🦖-Суслов Автор вопроса
Иван🦖 Суслов
14х14 больше 10 секунд

добваь несколько процесоров и потоков

Для нахождения кратчайшего пути есть алгоритм Дейкстры. Может подойти, если таблицу представить как граф, где ребра, это соседние клетки

еще почитай кроме дейкстры о A* (или просто a star algo)

я правильно понимаю, что прийти в любую клетку модно только из двух соседних (левой и верхней) и больше не из каких?

о это ДП

Иван🦖 Суслов
Верно

значит время работы алгоритма равняется количество клеток левее и выше *2

Похожие вопросы

Обсуждают сегодня

Господа, а что сейчас вообще с рынком труда на делфи происходит? Какова ситуация?
Rꙮman Yankꙮvsky
29
А вообще, что может смущать в самой Julia - бы сказал, что нет единого стандартного подхода по многим моментам, поэтому многое выглядит как "хаки" и произвол. Короче говоря, с...
Viktor G.
2
30500 за редактор? )
Владимир
47
а через ESC-код ?
Alexey Kulakov
29
Чёт не понял, я ж правильной функцией воспользовался чтобы вывести отладочную информацию? но что-то она не ловится
notme
18
У меня есть функция где происходит это: write_bit(buffer, 1); write_bit(buffer, 0); write_bit(buffer, 1); write_bit(buffer, 1); write_bit(buffer, 1); w...
~
14
Добрый день! Скажите пожалуйста, а какие программы вы бы рекомендовали написать для того, чтобы научиться управлять памятью? Можно написать динамический массив, можно связный ...
Филипп
7
Недавно Google Project Zero нашёл багу в SQLite с помощью LLM, о чём достаточно было шумно в определённых интернетах, которые сопровождались рассказами, что скоро всех "ибешни...
Alex Sherbakov
5
Ребят в СИ можно реализовать ООП?
Николай
33
https://github.com/erlang/otp/blob/OTP-27.1/lib/kernel/src/logger_h_common.erl#L174 https://github.com/erlang/otp/blob/OTP-27.1/lib/kernel/src/logger_olp.erl#L76 15 лет назад...
Maksim Lapshin
20
Карта сайта