貪婪的最佳子結構（optimal substructure）

假設你已經做了一個好決定，剩下同一個問題的較小版本。最佳子結構保證：把那個剩餘問題解到最佳，再黏到你的第一個決定上，就得到整個問題的最佳解。正是這個性質讓「一次一步」的方法得以運作：每一步都把問題縮小成同一類的較小實例。

精確地說：若一個問題的最佳解是由其子問題的最佳解組成，它就具有最佳子結構。對貪婪而言，你把這個性質與貪婪選擇性質配對。貪婪選擇性質說某個最佳解以貪婪選擇開頭；最佳子結構則說一旦那個選擇固定，剩下的是一個較小實例，其自身的最佳解能補完整個最佳值。兩者合起來證成歸納法：由歸納假設，貪婪在子問題上最佳；由貪婪選擇性質，貪婪的第一選擇可延伸成全域最佳；故貪婪整體最佳。以區間排程為例，挑了最早結束的工作並刪去所有與它重疊者後，你面對的正是剩餘工作上同樣的問題。

這正是動態規劃所倚賴的最佳子結構概念——兩種範式都需要它。差別在於貪婪還需要貪婪選擇性質，才能鎖定一個子問題而非嘗試許多個。提醒：許多問題有最佳子結構卻沒有貪婪選擇性質；0/1 背包是經典案例。單有最佳子結構只能帶你到動態規劃，本身並不准許貪婪。