Динамическое программирование: Лесенки, наибольшая возрастающая последовательность за O(nlog(n)), по подотрезкам, по подмножествам, ДП по поддереву. ДП по профилю, ДП по изломанному профилю
Динамическое программирование по профилю - способ оптимизации перебора количества вариантов с помощью динамического программирования, когда одно из измерений небольшое.
Профиль - один из столбцов (строк), удовлетворяющий условию задачи. Обычно используется в качестве состояния динамики.
Обычно дана таблица и надо посчитать количество замощений этой таблицы некоторыми фигурами (замощение шахматной доски доминошками). Можно перебрать все варианты и выбрать из них удовлетворяющие условию.
Но можно воспользоваться методом динамического программирования по профилю и сократить время по одной размерности до линейной.
Пусть у нас есть правило по которому надо заполнить и для него нам надо $k$ предыдущих линий. Тогда можно перебрать все замощения длиной $k\times n$. В итоге нужно заполнить данную таблицу этими замощениями. Получается, что если перебирать все варианты нам понадобиться $O(a^{nm})$ времени, а если перебирать только состояния и переходить по ним нам потребуется $O(a^{kn}*m)$ времени (где $а$ - количество способов замещения 1 клетки).
Реализация на Python
# Замощение доминошками прямоугольника N x M, ДП по прямому профилю: O(N * M * 4^M) по времени, O(2^M) по памяти.
def next_profiles(profile: int, width: int) -> list[int]:
# Маски следующей строки: клетки, куда уходят вертикальные доминошки, при заполнении строки.
result: list[int] = []
def fill(col: int, next_profile: int) -> None:
if col == width:
result.append(next_profile)
return
if (profile >> col) & 1: # клетка уже закрыта доминошкой из предыдущей строки
fill(col + 1, next_profile)
return
fill(col + 1, next_profile | (1 << col)) # вертикальная доминошка уходит вниз
if col + 1 < width and not ((profile >> (col + 1)) & 1): # горизонтальная доминошка вправо
fill(col + 2, next_profile)
fill(0, 0)
return result
def count_tilings(n: int, width: int) -> int:
# ways[p] - число способов заполнить строки сверху так, что в следующей строке закрыты клетки маски p.
ways = {0: 1}
for _ in range(n):
next_ways: dict[int, int] = {}
for profile, count in ways.items():
for next_profile in next_profiles(profile, width):
next_ways[next_profile] = next_ways.get(next_profile, 0) + count
ways = next_ways
return ways.get(0, 0)
def main() -> None:
for n, width in [(2, 3), (4, 4), (8, 8)]:
print(f"{n} x {width}: {count_tilings(n, width)} замощений")
if __name__ == "__main__":
main()
Реализация на C++
// Замощение доминошками прямоугольника N x M, ДП по прямому профилю: O(N * M * 4^M) по времени, O(2^M) по памяти.
#include <cstddef>
#include <cstdio>
#include <vector>
// Добавляет в out маски вертикальных доминошек следующей строки при заполнении строки с маской profile.
void collect_next_profiles(unsigned profile, std::size_t width, std::size_t col, unsigned next_profile,
std::vector<unsigned>& out) {
if (col == width) {
out.push_back(next_profile);
return;
}
if (((profile >> col) & 1u) != 0) { // клетка уже закрыта доминошкой из предыдущей строки
collect_next_profiles(profile, width, col + 1, next_profile, out);
return;
}
// вертикальная доминошка уходит вниз
collect_next_profiles(profile, width, col + 1, next_profile | (1u << col), out);
// горизонтальная доминошка уходит вправо
if (col + 1 < width && ((profile >> (col + 1)) & 1u) == 0) {
collect_next_profiles(profile, width, col + 2, next_profile, out);
}
}
// Число замощений прямоугольника n x width доминошками 1 x 2.
unsigned long long count_tilings(std::size_t n, std::size_t width) {
// ways[p] - число способов заполнить строки сверху так, что в следующей строке закрыты клетки маски p.
std::vector<unsigned long long> ways(std::size_t{1} << width, 0);
ways[0] = 1;
for (std::size_t row = 0; row < n; ++row) {
std::vector<unsigned long long> next_ways(ways.size(), 0);
for (unsigned profile = 0; profile < ways.size(); ++profile) {
if (ways[profile] == 0) continue;
std::vector<unsigned> next_profiles;
collect_next_profiles(profile, width, 0, 0, next_profiles);
for (unsigned next_profile : next_profiles) {
next_ways[next_profile] += ways[profile];
}
}
ways = next_ways;
}
return ways[0];
}
int main() {
// Проверка: 2 x 3 - 3 замощения, 4 x 4 - 36, 8 x 8 - 12988816.
const std::size_t sizes[][2] = {{2, 3}, {4, 4}, {8, 8}};
for (const auto& size : sizes) {
std::printf("%zu x %zu: %llu замощений\n", size[0], size[1], count_tilings(size[0], size[1]));
}
return 0;
}
Реализация на Rust
// Замощение доминошками прямоугольника N x M, ДП по прямому профилю: O(N * M * 4^M) по времени, O(2^M) по памяти.
/// Добавляет в next маски вертикальных доминошек следующей строки при заполнении строки с маской profile.
fn collect_next_profiles(profile: usize, width: usize, col: usize, next_profile: usize, next: &mut Vec<usize>) {
if col == width {
next.push(next_profile);
return;
}
if ((profile >> col) & 1) == 1 {
// клетка уже закрыта доминошкой из предыдущей строки
collect_next_profiles(profile, width, col + 1, next_profile, next);
return;
}
// вертикальная доминошка уходит вниз
collect_next_profiles(profile, width, col + 1, next_profile | (1usize << col), next);
// горизонтальная доминошка уходит вправо
if col + 1 < width && ((profile >> (col + 1)) & 1) == 0 {
collect_next_profiles(profile, width, col + 2, next_profile, next);
}
}
/// Число замощений прямоугольника n x width доминошками 1 x 2.
pub fn count_tilings(n: usize, width: usize) -> u64 {
// ways[p] - число способов заполнить строки сверху так, что в следующей строке закрыты клетки маски p.
let mut ways = vec![0u64; 1usize << width];
ways[0] = 1;
for _ in 0..n {
let mut next_ways = vec![0u64; 1usize << width];
for (profile, &count) in ways.iter().enumerate() {
if count == 0 {
continue;
}
let mut next_profiles = Vec::new();
collect_next_profiles(profile, width, 0, 0, &mut next_profiles);
for next_profile in next_profiles {
next_ways[next_profile] += count;
}
}
ways = next_ways;
}
ways[0]
}
fn main() {
// Проверка: 2 x 3 - 3 замощения, 4 x 4 - 36, 8 x 8 - 12988816.
for (n, width) in [(2usize, 3usize), (4, 4), (8, 8)] {
println!("{} x {}: {} замощений", n, width, count_tilings(n, width));
}
}