[Месяц изучения темы Golang] На выходных я попробовал ответить на несколько вопросов по динамическому программированию и отправил очень деликатную учебную версию. Ответ был очень хорошим. Далее я буду использовать два языка для вопросов по кодированию и чистке, а именно GO и JAVA , ребята, продолжайте писать вопросы.
Живите много дней - десять последовательных динамических программ - сверхтонкий анализ |
Какие вопросы вы можете решить с помощью динамического программирования?
1. Считать
- Сколько способов попасть в правый нижний угол
- Сколькими способами можно выбрать k чисел да и сложить
2. Найдите максимальное и минимальное значения
- Максимальная сумма чисел пути из левого верхнего угла в правый нижний угол
- самая длинная восходящая длина подпоследовательности
3. Ищите существования
- В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
- Можно ли выбрать k чисел так, чтобы сумма была суммой
4. Комплексное применение
- динамическое программирование + хэш
- динамическое программирование + рекурсия
- ...
leetcode 140. Разделение слов II
Имея непустую строку s и словарь wordDict, содержащий список непустых слов, добавьте пробелы в строку, чтобы составить предложение, в котором все слова в предложении находятся в словаре. Верните все эти возможные предложения.
проиллюстрировать:
Слова из словаря можно использовать повторно при разделении.
Можно считать, что в словаре нет повторяющихся слов.
Пример 1:
войти:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
выход:
[ "cats and dog", "cat sand dog" ]
Пример 2:
войти:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
выход:
[ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ]
Объяснение: Обратите внимание, что вы можете повторно использовать слова из словаря.
Пример 3:
войти:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
выход:
[]
--
Это сложный вопрос, сначала прочтитеслово разделить я
❤️❤️❤️❤️
2.1 Компонент динамического программирования 1: определение состояния
Проще говоря, при решении динамического программирования вам нужно открыть массив, что представляет собой каждый элемент массива f[i] или f[i][j] аналогично тому, что представляют x, y, z в математических задачах.
последний шаг
Мы определяем dp[i], чтобы указать, может ли строка s[0..i−1], состоящая из первых i символов строки s, быть разделена пробелами на несколько слов, которые встречаются в словаре.
Если разделение пробелов выполняется в позиции j, то чтобы определить, можно ли разбить s на одно или несколько слов, которые появляются в словаре пробелами, мы можем определить s[0 to j - 1] и s[j to i - 1 ] есть ли две части в словаре
s[0 to j-1] мы можем использовать идею динамического программирования, я храню предыдущий словарь
Например, s = "leetcode", wordDict = ["lee", "t", "code"]
[0 to j - 1] может относиться к двум словам ["lee", "t"], поскольку dp[0] = true, d[1] есть в словаре, поэтому уравнение перехода может быть следующим:
1.2 Компонент динамического программирования 2: уравнения перехода
dp[i]=dp[j] && проверить(s[j..i−1])
Проверка здесь может быть хеш-оценкой, находится ли перехваченная строка в массиве словаря.
1.3 Компонент динамического программирования 3: начальные условия и граничные случаи
dp[0] = true; пустая строка является правильной.
1.4 Компонент динамического программирования 4: Порядок вычислений
Вычислите по очереди, используйте i, чтобы пройти от 0 до j.
Код ссылки
языковая версия ГО
func wordBreak(s string, wordDict []string) (sentences []string) {
wordSet := map[string]struct{}{}
for _, w := range wordDict {
wordSet[w] = struct{}{}
}
n := len(s)
dp := make([][][]string, n)
var backtrack func(index int) [][]string
backtrack = func(index int) [][]string {
if dp[index] != nil {
return dp[index]
}
wordsList := [][]string{}
for i := index + 1; i < n; i++ {
word := s[index:i]
if _, has := wordSet[word]; has {
for _, nextWords := range backtrack(i) {
wordsList = append(wordsList, append([]string{word}, nextWords...))
}
}
}
word := s[index:]
if _, has := wordSet[word]; has {
wordsList = append(wordsList, []string{word})
}
dp[index] = wordsList
return wordsList
}
for _, words := range backtrack(0) {
sentences = append(sentences, strings.Join(words, " "))
}
return
}
Java-версия
public List<String> wordBreak2(String s, List<String> wordDict) {
// 为了快速判断一个单词是否在单词集合中，需要将它们加入哈希表
Set<String> wordSet = new HashSet<>(wordDict);
int len = s.length();
// 第 1 步：动态规划计算是否有解
// dp[i] 表示「长度」为 i 的 s 前缀子串可以拆分成 wordDict 中的单词
// 长度包括 0 ，因此状态数组的长度为 len + 1
boolean[] dp = new boolean[len + 1];
// 0 这个值需要被后面的状态值参考，如果一个单词正好在 wordDict 中，dp[0] 设置成 true 是合理的
dp[0] = true;
for (int right = 1; right <= len; right++) {
// 如果单词集合中的单词长度都不长，从后向前遍历是更快的
for (int left = right - 1; left >= 0; left--) {
// substring 不截取 s[right]，dp[left] 的结果不包含 s[left]
if (wordSet.contains(s.substring(left, right)) && dp[left]) {
dp[right] = true;
// 这个 break 很重要，一旦得到 dp[right] = True ，不必再计算下去
break;
}
}
}
// 第 2 步：回溯算法搜索所有符合条件的解
List<String> res = new ArrayList<>();
if (dp[len]) {
Deque<String> path = new ArrayDeque<>();
dfs(s, len, wordSet, dp, path, res);
return res;
}
return res;
}
/**
* s[0:len) 如果可以拆分成 wordSet 中的单词，把递归求解的结果加入 res 中
*
* @param s
* @param len 长度为 len 的 s 的前缀子串
* @param wordSet 单词集合，已经加入哈希表
* @param dp 预处理得到的 dp 数组
* @param path 从叶子结点到根结点的路径, 既然是队列，先进后出，需要保存叶子结点到根结点的路径，那么先进的是根节点
* @param res 保存所有结果的变量
*/
private void dfs(String s, int len, Set<String> wordSet, boolean[] dp, Deque<String> path, List<String> res) {
if (len == 0) { //
res.add(String.join(" ",path));
return;
}
// 可以拆分的左边界从 len - 1 依次枚举到 0
for (int i = len - 1; i >= 0; i--) {
String suffix = s.substring(i, len);
// 保证根节点或者叶子节点在集合中，dp[i] = true，表示并不会重复出现
// 因此len = 0时，即可将结果添加
if (wordSet.contains(suffix) && dp[i]) {
path.addFirst(suffix); // 先进根节点，再进叶子节点
dfs(s, i, wordSet, dp, path, res); // i--
path.removeFirst(); // 先移除叶子节点，在移除根节点
}
}
}
@Test
public void iswordBreak2() {
ArrayList a = new ArrayList<String>();
a.add("ab");
a.add("c");
a.add("a");
a.add("bc");
List<String> i = wordBreak2("abc", a);
Assert.assertNotNull(i);
}
❤️❤️❤️❤️
Большое спасибо, что смогли увидеть эту статью.Если эта статья хорошо написана и вы думаете, что есть что-то, пожалуйста, ставьте лайк👍 Следуйте ❤️ Пожалуйста, поделитесь 👥 Это действительно полезно для меня, красавчик Оппа! ! !
Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится!
В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. Как получить: GitHub github.com/Tingyu-Note…, следуйте официальной учетной записи для получения большего контента: Tingyu Notes, которые будут предоставляться один за другим.