Разделение заглавных букв на основе словаря


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

Я решил написать алгоритм, который принимает одну строку из заглавных букв, С, а разбить ее на подстроки, основанный на словаре, я предоставил. Мой алгоритм работает, как ожидалось, хотя я не уверен, если я использую правильно динамического программирования. Насколько я понимаю, ДП использует массив, который содержит решения подзадач более крупной проблемы. Это была моя цель с массивом результат. Вот моя простая программа, чтобы продемонстрировать решение проблемы:

import java.util.Scanner;

class WordBreak
{

    static String[] result;
    static String[] dictionary = {"I", "THE", "ABORT", "PLAN", "MEET", "CONFIRM", "AT",
                                  "DARK", "CABIN", "PROCEED", "MISSION", "MISS",
                                  "CHOCOLATE", "ALIENS", "CANNIBALS", "SAUCE"};

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        int size = str.length();
        result = new String[size];
        print(str, 0);
    }
    //method which recursively breaks input string into substrings
    //which are stored in an array and, if they are English words, then printed
    static void print(String str, int ind)
    {
        //each recursive call shortens the input string until length is 0
        int length = str.length();
        //if length is 0, then print the resulting substrings to decode
        //the message
        if(length == 0)
        {
            for(int i = 0; i < ind; i++)
            {
                System.out.print(result[i] + " ");
            }
            System.out.println();
            return;
        }
        //if a valid substring of the dictionary, add it to result array and recur
        for(int i = 1; i <= length; i++)
        {
            if(valid(str.substring(0, i)) == true)
            {
                result[ind] = str.substring(0, i);
                print(str.substring(i), ind + 1);
            }
        }
    }
    //valid function returns true iff string s is an English word (in the dictionary)
    static boolean valid(String s)
    {
        boolean result = false;

        for(int i = 0; i < dictionary.length; i++)
        {
            if(s.equals(dictionary[i]))
            {
                result = true;
                break;
            }
        }
        return result;
    }
}

Дана входная строка "ABORTTHEPLANMEETATTHEDARKCABIN" алгоритм делает качественно распечатать "прервать план встретиться в темной кабины".

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

И наконец (вроде не по теме), Что бы " о " Этот алгоритм будет? Мой анализ подсказывает мне, что либо \$o(п^2)\$ и \$o(П^3)\$ в зависимости от того, как вы смотрите на подстроки(я, J) вызов метода. Это для моего собственного любопытства, чтобы увидеть, если я анализирую его правильно.



97
3
задан 10 апреля 2018 в 12:04 Источник Поделиться
Комментарии
2 ответа

Ваш большой О примерно о(N^2) Если вы считаете свой словарь, чтобы быть статичным.

Я не вижу ничего в вашем решение, которое я бы классифицировал как динамического программирования. Может быть, вы могли бы сделать раствор ДП пре-парсинг свой словарь, так что вы не проверить подстрок несколько раз, но вместо того, чтобы проверить каждую букву от каждого-подходящее слово. Еще несколько тестовых случаев может оказаться несколько интересных багов тоже.

1
ответ дан 10 апреля 2018 в 02:04 Источник Поделиться

На основе этого поста кажется substring Это O(N) времени сложность (начиная с Java 7). Учитывая, что вы на самом деле работает substring(i,j)для каждого возможного i и j это означает, что общая временная сложность будет о(Н3).

Учитывая, что вы только фактически вызвать рекурсию, если текущая подстрока valid это не так плохо, как это выглядит хоть.


По данным Википедии:


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

Ваше текущее решение разбить ее на подпроблемы и использует решения, что было до текущей подстроки. Однако вы не повторно использовать все, что рассчитано для окончания ввода.

Со словарем у вас теперь это тоже не имеет значения.

Чтобы показать вам, что я имею в виду, давайте взглянем на другой искусственный словарь:

static String[] dictionary = {"A", "AB", "B", "CCC"};

Что произойдет, если мы используем входной строки "CCCABBCCC?

Вы найдете первый КХЦ раз это хорошо. Затем вы начинаете обращение "а". Вы найдете "б", другой "Б" и "СТС".

Ваш алгоритм делает шаг назад, сразу после "опять СТС" и находит "АБ". Теперь он должен искать возможных wordts в последние 4 буквы снова, но мы уже проверили это право раньше!

Решение ДП будет иметь способ хранить все возможные решения, найденные для каждого "будущего индекса".

Важная вещь, чтобы отметить здесь заключается в том, что он не должен быть массивом. Это может быть возможно, пока вам не нужно, чтобы вычислить этот "подзадача" во второй раз.


Я согласен с комментарием на mtj, что эта проблема не очень сильно выиграть от использования динамического программирования. Есть большие затраты памяти для хранения результатов суб, который вы, вероятно, никогда не использовать.

Найти числа Фибоначчи-один из самых очевидных простых примеров, которые массово получают из методом динамического программирования. Ну, по крайней мере, если вы хотите найти более 1 количество привирать и хотите использовать любые расчеты не найти ранее введенного числа. Не использовать ДП для нахождения одного привирать количество, так как вы можете решить за o(n) с просто хранить предыдущие 2 шага.

1
ответ дан 10 апреля 2018 в 07:04 Источник Поделиться