動的計画法（基礎）”まで”を状態として扱う, 状態の拡張
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,247文字 🖼 2枚の画像
続きは購入後に閲覧できます。
この教材を購入 ↗