プロンプトと適用範囲
棒の端点は 0 と n であり、cuts には重複のない内部の位置が含まれます。各ステップで、現在の区間内の切断点を1つ選択し、その区間の長さをコストとして支払って2つの区間に分割します。LeetCode 1547 の規模を想定します：n は最大 1,000,000、切断の数 m は最大 100 です。最小コストのみを返します。順序を復元するには決定点を保存する必要があります。
面接官が見ているポイント
- 入力の順序に貪欲（greedy）に従うのではなく、区間DPを見抜けるかどうか。
- 番兵として 0 と n を追加し、切断位置をソートするかどうか。
- 最初（または最後）の切断を選択することで問題が独立した区間に分割される理由を説明できるかどうか。
- m に基づく時間計算量、空間計算量、および整数の安全性に関する制限を提示できるかどうか。
確認すべき質問
- cuts に 0、n、または重複が含まれる可能性はありますか？その場合、APIは重複を排除すべきですか、それとも拒否すべきですか？
- 最小コストのみが必要ですか、それとも1つの最適順序も必要ですか？後者の場合は選択テーブルが必要です。
- m の上限は何ですか？m がより大きい場合、3乗時間は除外される可能性があります。
- 各切断のコストは正確に現在の区間の長さですか？重み付きコストの場合は遷移が変わります。
30秒での回答
切断位置をソートし、0 と n を追加します。dp[i][j] を点 i と j の厳密な間にあるすべての切断を行う最小コストとし、隣接する端点の値は 0 とします。各区間について、内部の各ピボット k を最初の切断点として試します。その切断には区間の長さのコストがかかり、左右の区間は独立しているため、dp[i][k] と dp[k][j] を加算します。区間の長さ（スパン）を昇順に埋めることで、O(m cubed) の時間と O(m squared) の空間で dp[0][m+1] が得られます。
詳細な解説
1. 座標と不変条件の確立
cuts をソートし、0、すべての切断位置、n を含む points を構築します。ソート後、points[i] から points[j] までの区間の内部切断点は、正確に i と j の間にあるインデックスとなります。この不変条件により、状態はそれ以前の切断の履歴ではなく、端点に依存するようになります。
2. 区間状態の定義
dp[i][j] は、points[i] と points[j] の厳密な内側にあるすべての切断を行う最小コストです。j が i プラス 1 のときは内部切断点がないため、値は 0 です。最初の切断の後、左右の部分問題は相互作用せず、以降の各コストは現在の区間にのみ依存するため、状態に順序を記録する必要はありません。
3. 遷移の導出
最初の切断点が points[k]（ただし i < k かつ k < j）である場合、現在の支払いは points[j] マイナス points[i] です。この切断により、2つの独立した区間が生成されます：
dp[i][j] = min(
dp[i][k] + dp[k][j] + points[j] - points[i]
for k in (i + 1 ... j - 1)
)両方の部分区間の値がすでに利用可能であるように、より短いスパンから順に計算します。
4. 実装
function minCost(n: number, cuts: number[]): number {
const points = [0, ...cuts.slice().sort((a, b) => a - b), n];
const m = points.length;
const dp = Array.from({ length: m }, () => Array<number>(m).fill(0));
for (let span = 2; span < m; span += 1) {
for (let left = 0; left + span < m; left += 1) {
const right = left + span;
let best = Number.POSITIVE_INFINITY;
for (let pivot = left + 1; pivot < right; pivot += 1) {
best = Math.min(
best,
dp[left][pivot] + dp[pivot][right] + points[right] - points[left],
);
}
dp[left][right] = best === Number.POSITIVE_INFINITY ? 0 : best;
}
}
return dp[0][m - 1];
}5. 遷移の証明
内部切断の数に関する数学的帰納法を用います。切断が0個の場合、コストは0です。より短い区間が最適であると仮定します。すべての最適な順序には最初のピボット k が存在します。そのコストは区間全体の長さとして固定されます。残りの作業は左右の区間に分割され、帰納法によりそれらの最適値は dp[i][k] と dp[k][j] になります。すべての可能な k について最小値を取ることであらゆる最初の切断が網羅されるため、この遷移は最適です。
6. 計算量、数値、および復元
m 個の内部切断がある場合、O(m squared) 個の状態があり、状態あたり最大 O(m) 個のピボットが存在するため、O(m cubed) の時間と O(m squared) の空間になります。n が最大 1,000,000 で m が最大 100 の場合、JavaScript の number で指定されたコスト範囲をカバーできます。より大きな重み付きコストの場合は、BigInt または明示的な安全整数チェックを使用します。順序を復元するには、各最小値を達成したピボットを保存し、決定木を再帰的に出力します。
7. 反例とテスト
n=7 かつ cuts=[1,3,4,5] の場合、入力順に切断するとコストは 20 になりますが、順序 3,5,1,4 ではコストは 16 になります。これにより、入力順や左から右への貪欲法による選択が誤りであることが証明されます。また、切断が1つだけの場合、端点付近の位置、ソートされていない入力、重複ポリシー、連続するギャップ、最大 m、および内部切断のない基本区間もテストします。
模範解答
切断位置をソートし、0 と n を追加します。dp[i][j] は2つの端点間にあるすべての切断の最小コストであり、隣接する端点では 0 です。各区間について、ピボット k を最初の切断点として試します。区間の長さを支払い、最適な左右のコストを加算します。スパンを増やしながら埋めることで、最も外側の区間の値が得られます。m 個の切断がある場合、計算量は O(m cubed) 時間と O(m squared) 空間です。各最適ピボットを保存することで順序を復元できます。ソートされていない入力、端点付近の切断、単一の切断、および n=7, [1,3,4,5] の反例をテストします。
よくある間違い
- 入力順に切断する → その順序は最適とは程遠い可能性があります → ソートし、区間DPで最初のピボットを列挙します。
- 0 と n を省略する → 境界の長さと状態が不完全になります → 両端点を番兵として含めます。
- dp を1回の切断コストのみとして定義する → 後続の切断が省略されます → 内部集合全体に対する最小コストとして定義します。
- 最短または最長のセグメントを貪欲に選択する → 局所的な選択が両方の部分問題のコストを変化させます → 再帰的分割と帰納法の証明を示します。
- ソートされた入力のみをテストする → コードが暗黙のうちに順序を前提とする可能性があります → 関数内でコピーしてソートし、ソートされていない配列でテストします。
フォローアップ質問
最適な切断順序を1つ返すにはどうすればよいですか？
各区間の最小値を達成したピボットを保存します。そのピボットを出力し、左右の区間を再帰的に処理します。複数のピボットでタイ（同値）が発生した場合は、最小のインデックスや辞書順で最小の順序など、決定論的なルールを定義します。
m が 100 から 2,000 に増加した場合、O(m cubed) は許容されますか？
計測せずに保証してはいけません。状態数と時間制限を見積もり、追加の構造、近似、またはオフラインの制約を探します。一般的な O(m squared) の主張には、証明された単調性または四角不等式（quadrangle inequality）の性質が必要です。
cuts に重複する位置が含まれている場合はどうなりますか？
重複した切断には2回目の物理的な効果はありません。入力規約に従ってソートして重複を排除するか、重複を拒否します。長さ0の区間を作成するのではなく、選択した処理を文書化してテストします。
各切断のコストがセグメント長に重みを掛けたものである場合はどうなりますか？
重みが選択されたピボット k にのみ依存する場合、区間長の項を区間長 × weight[k] に置き換えても、分割は独立したままです。コストが履歴、切断回数、または区間をまたぐ状態に依存する場合、部分問題はもはや独立しておらず、状態の再設計が必要です。