Я находил перевод этой статьи, однако из-за неполного перевода думал что там подсчитывается вариант расстановки фигур без учета "ни один не бьет других". Этот вариант не подходит. Данная задача изначально написана на русском и в ней считается просто возможность расставить слонов, не учитывается что слоны не должны не бить друг друга. Это проявляется в различии в числах ответов моего результата и приведенного алгоритма. А так же становится понятно, если разобрать динамику. Ну либо я крайне неправильно понял её.

Чет сильно смущает меня это условие про бой. Сильно модифицируется количество доступных ячеек после установки очередной фигуры и я не могу найти универсального правила, чтобы не высчитывать каждое положение.

Чего... Когда там написано что ставим слонов, там уже подразумевается что ставим слонов которые не бьют друг друга

Иначе какая разница что это слоны :)

ну просто расставить слонов это C(N^2/2, 3) (для четной N) 🙂

Почему не C(n^2, 3)? Ставить то можно на любые клетки

Чет ночь без сна дает о себе знать, сорян. Тогда мне осталось адаптировать это решение под тот факт, что нужно теперь учитывать что слоны должны быть все одного цвета. В том решении слоны ставятся параллельно на белые и черные клетки.

2*C(n^2 /2,3)

Слоны одного цвета (но не сказано какого)

Там в решение считаются две независимые динамики

По факту

А нельзя посчитать наоборот? C(n^2 /2,3) минус число способов которыми бьются? Интуитивно кажется что это попроще.

Белые, слоны белые. И первая клетка тоже белая.

в условии один цвет, тогда C(N^2/2, 3)*2 🙂

Сделал все-таки эту задачу, адаптировав решение по ссылке. Когда по ссылке результат суммировался в процессе обхода двух динамик, по белым и черным полям, в моем же случае диагонали были только одни и я сразу брал последний элемент из первой динамики. Проверил руками на малых значениях - работает.
Сорян за ночной тупняк, это моя первая задача по динамическому программированию и даже имея решение перед глазами разобраться в нем сложно.

Поделитесь, какие курсы по алгоритмам на русском языке вы считаете наилучшими? Интересуют максимально полные курсы, а не уровень "грокаем алгоритмы".

Уж очень плохо я книжки воспринимаю. Лекции куда интереснее слушать

https://codeforces.com/edu/courses достаточно продвинутый

смотри лекции Паши Маврина на ютубе, он и в cs препал и в Итмо, если будешь хорошо искать, мб, даже найдешь домашки по лекциям, но тут не гарантирую

Интересно. Не видел его записей в csc