切鋼條問題（rod-cutting problem）

你有一根整數長度為 n 的金屬鋼條，以及一張價目表，告訴你每種長度的一段能賣多少：長度 1 賣 price[1]、長度 2 賣 price[2]，依此類推。你可以把鋼條切成任意數量的整數長度段（或保持整根不切），你想選出能讓總收益最大的切法。讓它有趣的轉折在於，價格並非與長度成正比——有時兩段短的比一段長的值錢，有時反過來——所以你必須真的去搜尋該怎麼切。

它有乾淨的最佳子結構：長度 n 鋼條的最佳收益，是先切下某個長度 i 的一段（1 <= i <= n）、收取該段的 price[i]，再把剩下的長度 n - i 最佳地切。由於你不知道最佳的第一段是哪個，你就全部試過、保留最佳。令 r(n) 為長度 n 的最大收益。則 r(n) = 在 i 從 1 到 n 中取 ( price[i] + r(n - i) ) 的最大值，基底情況為 r(0) = 0。同樣的 r(k) 值會被許多較長的鋼條需要（重疊），所以動態規劃很合適：依遞增順序填 r[0], r[1], ..., r[n]，每格掃過可能的第一刀。共有 n+1 個狀態、每個做 O(n) 工作，所以整體是 O(n^2)——比暴力法約 2^(n-1) 種切法是巨大的改進。

切鋼條是費氏數式一維動態規劃通往更豐富問題的經典橋樑：與費氏數不同，它的轉移涉及在許多選擇間取最大值，而非固定的求和，這是學習者第一次遇到「試每一個第一步、取最佳」。要還原真正的切法，為每個長度存下達成最大值的第一刀大小，再往下走：切下那個大小、移到剩餘、重複。同樣的模板——選第一段、對其餘遞迴——會再現於硬幣找零與無限背包，所以在這裡花心力理解它的回報會一再出現。