Динамическое программирование для разделения строки на список отдельных слов

Question

Это в основном дубликат:

Как разбить строку на слова. Пример: "stringintowords" -> "Строка в слова"?

neverthelees, у меня есть такая функция: public int Word(x) {code}, где для строки x она возвращает целое число (+ ve или -ve), и это целое число будет указывать на то, насколько хорошо или плохо разбиение для конкретного слова. Я должен вернуть комбинацию, которая дает максимальное число.

Что я думал для этого, так это создать таблицу (i, j), где i и j имеют длину слова, и заполнить таблицу крачкой, как:

for i = 1 to n
   for j=i to n do 
      word(subset of x i to j)

и, тем не менее, заполните таблицу, как я смогу когда-нибудь найти оптимальное решение (рекурсивным способом?)

любая помощь приветствуется.

РЕДАКТИРОВАТЬ: оптимальный путь - это путь с наибольшей суммой функции слова (x), т. Е. Если у нас есть
путь (1,3) = 10, (3,6) = 20, (6,7) = 1 и
путь (1,1) = 0, (2,5) = 12, (5,7) = - 1
тогда сумма 1-го пути> 2-го

РЕДАКТИРОВАТЬ2: Я хотел бы, чтобы все знали, что я ответил на этот вопрос после долгих часов работы, несмотря на то, что я не нашел решения, я думаю, что получить его самостоятельно всегда лучше:

ура!)

Answer 1

хорошо, позвольте мне привести пример:

word thetree


         1  2   3  4  5  6  7 ( ending index)

start 1  1  -1  2 -1 -1 -1 -1
      2  0  1  -1  -1 -1 -1 -1
      3  0  0   1  0  0  0  0
      4  0  0   0  1  0  0  4
      5  0  0   0  0  1  0  0
      6  0  0   0  0  0  1  0  
      7  0  0   0  0  0  0  1

хорошо рассмотрите это решение, тогда, если вы храните каждый столбец отдельно, то при столбце номер 3 вы получаете 2, а в 7 вы получаете 4, что даетвсего 6, тем не менее, если вы берете каждую букву отдельно, то: 1 + 1 + 1 + 1 + 1 + 1 + 1 = 7 (по диагонали вниз i = j), что означает, что тальба неверна ...

это могло бы сработать, если бы я мог сохранить только позицию предыдущего энтера, которая была лучшей. (Опять же, я думаю)

Answer 2

Сэм, вы говорите, что:

у вас есть таблица, заполненная вашей позицией в строке, и логические значения для каждой ячейки, если есть подстрока длины j.

* * 1004 пример: * * 1005

                    |       Positions of the example:
                    |            "xdeafcatmonologue"
 -------------------|-------------01234567890123476----------------
length of substring |                              
        1           |             11111111111111111     
        2           |             ------2----------
        3           |             -----3------3----
        4           |             -4--------------- 
        5           |             -----------------
        6           |             -----------------
        7           |             -----------------
        8           |             -----------------
        9           |             --------9--------
                    |              

      final         |             -4---3--9---3----

Черточки - это технически нули, а числа чисел - это таблица, которую вы будете строить.

Вы можете построить таблицу намного меньшего размера, если сохраните только максимальное значение для каждой позиции, потому что ваша функция Word сообщает вам максимум для каждой позиции. Не имеет значения, перебираете ли вы размер подстроки, свою переменную j, потому что Word не использует j.

Пожалуйста, исправьте меня, если я ошибаюсь с любым из этих предположений.