#algorithm #tree #binary-tree #dynamic-programming
Вопрос:
Я пытаюсь решить следующую проблему. Я не буду врать, что это домашнее задание. Я спрашиваю не об ответе, а, по крайней мере, о некоторых советах и о том, как я могу начать думать о проблеме.
Двоичное дерево, каждый узел которого помечен целым числом, называется помеченным. Набросайте алгоритм динамического программирования, решающий следующую задачу :
Дано: последовательность b1; … ; bm целых чисел и помеченных двоичных деревьев T1; … ; Tk высоты 1
Решите: существует ли помеченное двоичное дерево, имеющее в качестве каждого из поддеревьев высотой 1 некоторое Ti (с разрешенными повторениями) и имеющее b1; … ; bm в качестве меток своих листьев.
Дается следующая подсказка: черпайте вдохновение из алгоритма цепочки матриц и подумайте о таблице, в которой в качестве каждой записи указан набор целых чисел, каким-то образом относящихся к подпоследовательности bi; … ; bi s.