[Месяц изучения темы Golang] На выходных я попробовал ответить на несколько вопросов по динамическому программированию и отправил очень деликатную учебную версию. Ответ был очень хорошим. Далее я буду использовать два языка для вопросов по кодированию и чистке, а именно GO и JAVA , ребята, продолжайте писать вопросы.
Живите много дней - десять последовательных динамических программ - сверхтонкий анализ |
Какие вопросы вы можете решить с помощью динамического программирования?
1. Считать
- Сколько способов попасть в правый нижний угол
- Сколькими способами можно выбрать k чисел да и сложить
2. Найдите максимальное и минимальное значения
- Максимальная сумма чисел пути из левого верхнего угла в правый нижний угол
- самая длинная восходящая длина подпоследовательности
3. Ищите существования
- В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
- Можно ли выбрать k чисел так, чтобы сумма была суммой
литкод 131. Разделенный палиндром
Дана строка s, пожалуйста, разбейте s на подстроки так, чтобы каждая подстрока была палиндромом. Вернуть все возможные схемы разбиения для s.
Палиндром — это строка, которая одинаково читается вперед и назад.
Пример 1:
Ввод: с = "ааб"
Вывод: [["а","а","б"],["аа","б"]]
Пример 2:
Вход: с = "а"
Вывод: [["а"]]
намекать:
1 <= s.length <= 16
s состоит только из строчных английских букв
--
Код ссылки
языковая версия ГО
func partition(s string) (ans [][]string) {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
for j := range f[i] {
f[i][j] = true
}
}
for i := n - 1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
f[i][j] = s[i] == s[j] && f[i+1][j-1]
}
}
splits := []string{}
var dfs func(int)
dfs = func(i int) { // 1.
if i == n {
ans = append(ans, append([]string(nil), splits...))
return
}
for j := i; j < n; j++ { //
if f[i][j] { // 2.
splits = append(splits, s[i:j+1]) // 3.
dfs(j + 1)
splits = splits[:len(splits)-1] // 4.
}
}
}
dfs(0)
return
}
Java-версия
class Solution {
boolean[][] dp;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
dp = new boolean[n][n];
char[] charArray = s.toCharArray();
for (int i = 0; i < n; i++) {
dp[i][i] = true; // 对本身来说就是回文
}
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1]; // 要满足这个条件,必需先满足j - i > 3考虑边界
}
}
}
}
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (dp[i][j]) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
}
❤️❤️❤️❤️
Большое спасибо, что смогли увидеть эту статью.Если эта статья хорошо написана и вы думаете, что есть что-то, пожалуйста, ставьте лайк👍 Следуйте ❤️ Пожалуйста, поделитесь 👥 Это действительно полезно для меня, красавчик Оппа! ! !
Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится!
В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. Как получить: GitHub github.com/Tingyu-Note…, следуйте официальной учетной записи для получения большего контента: Tingyu Notes, которые будут предоставляться один за другим.