動的計画法に基づくアルゴリズム問題集と実装パターン
矩形分割問題
与えられた $N \times M$ の矩形を、縦または横に分割する操作を繰り返して特定の面積 $K$ を得るまでの最小コストを求める問題である。$N, M$ が小さいため、状態をメモ化する再帰関数を用いて分割位置を全探索するアプローチが有効である。各ステップで左右または上下に切り分け、分割線に沿ったコストを加算しながら再帰的に遷移する。
#include <iostr ...
7月21日 00:04 投稿
桁DPの基礎と応用
桁DPとは何か？
桁DP（Digit Dynamic Programming）は、通常ある区間[L, R]内で特定の制約を満たす数字の数を統計するために使用されます。LとRのデータ範囲が大きいため、DP（動的計画法）で統計する必要があることが多いです。
上限Rの処理テクニック
数値の比較ルールから、現在の桁の取りうる値の範囲は、前方の桁の値に依存することがわかります。
もし前方のすべて ...
6月25日 20:48 投稿