動的計画法（基礎）”まで”を状態として扱う, 状態の拡張
LeetCode 練習問題集
| 問題 | 難易度 | 重要度 | テクニック |
|---|---|---|---|
| House Robber | ★★★ | 高 | ”まで”を状態として扱う |
| House Robber II | ★★★ | 高 | ”まで”を状態として扱う |
| Decode Ways | ★★★ | 高 | ”まで”を状態として扱う |
| Word Break | ★★★ | 高 | ”まで”を状態として扱う |
| Maximum Product Subarray | ★★★ | 高 | ”まで”を状態として扱う |
| Coin Change | ★★★ | 高 | 状態の拡張 |
| Minimum Cost For Tickets | ★★★ | 高 | 状態の拡張 |
| Minimum Number of Coins to be Added | ★★★ | 高 | 状態の拡張 |
”まで”を状態として扱う
今までの問題は全て「i番目”の”何々」といった形で、状態がi番目とすごくシンプルなものでした。ここでは少し複雑な「i番目”まで”の何々」を状態として扱っていきます。
実はコード上では”まで”と”の”はあまり相違がありません。また動的計画法（基礎）貰うDP, 配るDP で紹介した問題もi番目”まで”と言い換えることも可能です。それでもなぜわざわざ”まで”を強調したかというと、多くのDPにまだ馴染みのない方はこのi番目”まで”を状態として扱う感覚がなく、その様なDPの問題が出されてもDPだとすぐに判断できないからです。
実際に例題を見てみましょう。
例題. House Robber
難易度: ★★★ 重要度: 高
この続きは、購入者向けの内容です。
非表示コンテンツ 📝 11,233文字 🖼 2枚の画像
続きは購入後に閲覧できます。
この教材を購入 ↗