LeetCode 練習問題集
問題 | 難易度 | 重要度 | テクニック |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★ | 高 | 二次元状態DP | |
★★★★★ | 中 | 二次元状態DP |
二次元状態DP
今まで扱った問題の状態は全て一次元でした。ここでいう一次元とはdp(i)といった形で、状態を構成する要素が
iの1つしかないことを意味します。実際の問題では状態を構成する要素が複数存在することがあります。例えばこれから解説する二次元状態DPでは、dp(i, j)という様に状態を構成する要素が2つとなる問題を扱います。状態を構成する要素が増えればその分だけ遷移式の立式も複雑になり、問題も難しくなります。本章では有名で典型的な二次元状態DPの例題をいくつか扱います。また練習問題では様々な二次元状態DPに触れて慣れることを目的として、例題と密接な関係が無い問題も出題しています。
例題1. Knapsack Problem（ナップザック問題）
難易度: ★★★ 重要度: 高
