@Origin Вы можете ожидать, что каждое число будет ребром графа, так как я должен получить максимальный маршрут, и я не могу оглянуться назад, пирамида оказывается DAG, выполняет DFS для получения топологической сортировки, а затем использует ее для получения кратчайший путь графика вы можете получить его быстрее, чем решение для динамического программирования
я есть такая цифровая пирамида
7
4 8
1 8 9
2 4 6 7
4 6 7 4 9
4 9 7 3 8 8
routes: 32
каждое число индексируется тем, насколько мощно в его строке.
0 ( 9 => 1 ) 1 ( 8 => 5 ) 2 ( 8 => 4 ) 3 ( 7 => 2 ) 4 ( 4 => 0 ) 5 ( 3 => 3 )
0 ( 9 => 4 ) 1 ( 7 => 2 ) 2 ( 6 => 1 ) 3 ( 4 => 3 ) 4 ( 4 => 0 )
0 ( 7 => 3 ) 1 ( 6 => 2 ) 2 ( 4 => 1 ) 3 ( 2 => 0 )
0 ( 9 => 2 ) 1 ( 8 => 1 ) 2 ( 1 => 0 )
0 ( 8 => 1 ) 1 ( 4 => 0 )
0 ( 7 => 0 )
в этой пирамиде есть 2 ^ (n-1) маршрутов (вы можете пройти 2 пути от каждого числа). Если эта пирамида высока так низко, вы можете легко рассчитать все маршруты и сравнить их друг с другом. Но если у вас 50 пирамид с маршрутами 562949953421312, проблема немного сложнее.
Я думаю, что начинаю снизу, начиная с самых сильных чисел, но вскоре я понял, что максимальная стоимость маршрута не обязательно начинается или заканчивается большими числами.
Тогда я подумал, что, возможно, помогут вторичные индексы (куда вы можете пойти дальше от числа), но я даже не реализовал это, потому что предположил, что он все еще использует много ресурсов и не оптимален.
И теперь я запутался, как начать думать об этой проблеме ... любой совет приветствуется