動的計画法（基礎）二次元状態DP

LeetCode 練習問題集

問題	難易度	重要度	テクニック
0-1 Knapsack Problem	★★★	高	二次元状態DP
Best Time to Buy and Sell Stock with Transaction Fee	★★★	高	二次元状態DP
Largest Square	★★★	高	二次元状態DP
Knapsack Problem	★★★	高	二次元状態DP
Best Time to Buy and Sell Stock with Cooldown	★★★	高	二次元状態DP
Unique Paths	★★	高	二次元状態DP
Longest Common Subsequence	★★★	高	二次元状態DP
Edit Distance	★★★	高	二次元状態DP
Interleaving String	★★★	高	二次元状態DP
Distinct Subsequences	★★★	高	二次元状態DP
Regular Expression Matching	★★★★★	中	二次元状態DP

二次元状態DP

今まで扱った問題の状態は全て一次元でした。ここでいう一次元とはdp(i)といった形で、 状態を構成する要素がiの1つしかない ことを意味します。実際の問題では状態を構成する要素が複数存在することがあります。例えばこれから解説する二次元状態DPでは、dp(i, j)という様に状態を構成する要素が2つとなる問題を扱います。

状態を構成する要素が増えればその分だけ遷移式の立式も複雑になり、問題も難しくなります。本章では有名で典型的な二次元状態DPの例題をいくつか扱います。また練習問題では様々な二次元状態DPに触れて慣れることを目的として、例題と密接な関係が無い問題も出題しています。

例題1. Knapsack Problem（ナップザック問題）

難易度: ★★★ 重要度: 高