▲

3

▼

🎯 Динамическое программирование для подсчёта "хороших строк"

leetcoder, 31-12-2024 , 284

Сегодня нас опять радует задачка на методы динамического программирования - 2466. Count Ways To Build Good Strings.

😊 Описание задачи

Нам нужно подсчитать количество "хороших строк", длина которых находится в диапазоне [low, high].
Хорошая строка создаётся из пустой строки путём выполнения следующих операций:

• Добавление символа '0' ровно zero раз.
• Добавление символа '1' ровно one раз.

Результат может быть очень большим, поэтому необходимо вернуть его по модулю 10⁹+7.

💡 Идея

Для решения задачи мы используем динамическое программирование.
Каждое состояние dp[length] хранит количество способов построить строку длины length.
Постепенно вычисляя значения для всех длин от 1 до high, мы получаем итоговый результат.

🔍 Подробности подхода

1. Инициализация:
   • Создаём массив dp длиной high+1, где dp[length] будет содержать количество способов построить строку длины length.
   • Базовый случай: dp[0] = 1, так как существует ровно один способ создать пустую строку.
2. Основной цикл:
   • Для каждой длины length от 1 до high:
     • Если возможно добавить zero символов '0', добавляем вклад из dp[length - zero].
     • Если возможно добавить one символов '1', добавляем вклад из dp[length - one].
3. Подсчёт результата:
   • Подсчёт производим внутри основого цикла вычислений таблицы ДП.
   • Если текущая длина находится в диапазоне [low, high], добавляем её вклад в итоговый результат.

⏱ Асимптотика

• Временная сложность: O(high)
  • каждый индекс массива dp вычисляется один раз.
• Пространственная сложность: O(high)
  • используется массив длиной high+1.

💻 Исходный код

impl Solution {
    pub fn count_good_strings(low: i32, high: i32, zero: i32, one: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;

        // Convert input values to usize for indexing
        let low = low as usize;
        let high = high as usize;
        let zero = zero as usize;
        let one = one as usize;

        // DP array: dp[length] stores the number of ways to construct strings of length `length`
        let mut dp = vec![0; high + 1];
        dp[0] = 1; // Base case: one way to construct an empty string

        // Accumulate the result for valid lengths
        let result = (1..=high)
            .fold(0, |mut acc, length| {
                let mut current = 0;

                // Add contributions from `length-zero` and `length-one` if valid
                if length >= zero {
                    current = dp[length - zero];
                }
                if length >= one {
                    current = (current + dp[length - one]) % MOD;
                }

                // Store the computed value in dp[length]
                dp[length] = current;

                // Add to result if `length` is within the range [low, high]
                if length >= low {
                    acc = (acc + current) % MOD;
                }

                acc
            });

        result
    }
}