Усовершенствованное динамическое программирование — сегментация палиндромных строк II｜Go Theme Month

Go

[Месяц изучения темы Golang] На выходных я попробовал ответить на несколько вопросов по динамическому программированию и отправил очень деликатную учебную версию. Ответ был очень хорошим. Далее я буду использовать два языка для вопросов по кодированию и чистке, а именно GO и JAVA , ребята, продолжайте писать вопросы.

Если вы не знакомы с динамическим программированием, перейдите к этой статье.\color{red}{Если вы не знакомы с динамическим программированием, перейдите к этой статье~}

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

Это классика 😄😄😄\color{green}{Это очень классический вопрос 😄 😄 😄 ~}

Какие вопросы вы можете решить с помощью динамического программирования?

1. Считать

  • Сколько способов попасть в правый нижний угол
  • Сколькими способами можно выбрать k чисел да и сложить

2. Найдите максимальное и минимальное значения

  • Максимальная сумма чисел пути из левого верхнего угла в правый нижний угол
  • самая длинная восходящая длина подпоследовательности

3. Ищите существования

  • В игре со сбором камней обязательно ли выиграет тот, кто сделает первый ход?
  • Можно ли выбрать k чисел так, чтобы сумма была суммой

leetcode 132. Расщепление палиндромов II

Дана строка s, пожалуйста, разбейте s на подстроки так, чтобы каждая подстрока была палиндромом.

Возвращает минимальное количество разбиений, соответствующих требованиям.

 

Пример 1:

Ввод: с = "ааб"

выход: 1

Объяснение: Чтобы разбить s на две палиндромные подстроки, такие как ["aa","b"], достаточно одного разбиения.

Пример 2:

Вход: с = "а"

вывод: 0

Пример 3:

Ввод: с = "аб"

выход: 1  

намекать:

1 <= s.length <= 2000

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.
            }
        }
    }
     f := make([]int, n)
    for i := range f {
        if g[0][i] {
            continue
        }
        f[i] = math.MaxInt64
        for j := 0; j < i; j++ {
            if g[j+1][i] && f[j]+1 < f[i] { // j+ 1的原因是，不用从0开始，我们已经判断了f[0][i]了
                f[i] = f[j] + 1  // 这里请看上面说明。
            }
        }
    }
    return f[n-1]

}

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考虑边界
                    }
                }
            }
        }
        int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {  // j+ 1的原因是，不用从0开始，我们已经判断了f[0][i]了
                        f[i] = Math.min(f[i], f[j] + 1);  // 这里请看上面说明。
                    }
                }
            }
        }
        return f[n - 1];
    }
    
}

❤️❤️❤️❤️

Большое спасибо, что смогли увидеть эту статью.Если эта статья хорошо написана и вы думаете, что есть что-то, пожалуйста, ставьте лайк👍 Следуйте ❤️ Пожалуйста, поделитесь 👥 Это действительно полезно для меня, красавчик Оппа! ! !

Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и советуйте, это очень ценится!

В конце статьи мы недавно составили материал для интервью «Руководство по прохождению интервью по Java», в котором рассматриваются основные технологии Java, JVM, параллелизм Java, SSM, микросервисы, базы данных, структуры данных и многое другое. Как получить: GitHub github.com/Tingyu-Note…, следуйте официальной учетной записи для получения большего контента: Tingyu Notes, которые будут предоставляться один за другим.

Категории