如果賣出長度是 i 的 rod 可以得 pi 元，怎麼切一條長度是 n 的 rod 使總收入最大
方法一、遞迴
最直觀的方式就是用遞迴解，如下圖所示，rn 為切割長度 n 的 rod 可得的最大收入，假設 i 為最佳解中的第一段長度，rn = pi + rn-i，因為 pi 是切割的最佳解中第一段的獲利，再加上剩餘部分最佳獲利就是我們要的答案。
i 怎麼求？利用迴圈讓 i 從 0 跑到 n-1，求出每一組 pi + rn-i，找到最大的那組就是答案。
但這樣會遇到一個問題，每一次的 rn-i 都需要遞迴下去找到他的最佳解，這樣重複的 r 就會需要算很多次，以下圖為例，算 r4 的時候需要算 r3, r2, r1, r0，算 r3 又要再算一次 r2, r1, r0，因此我們需要利用 DP 來幫我們節省時間。
方法二、DP
我們可以建表紀錄每一個 ri 的數值，這樣就不用每次遇到 i 都再算一次
已知 r0, r1，就可以利用 r0, r1 算 r2，r2 = max( p1+r1, p2+r0 )，再來利用 r1, r2 算 r3，最後就知道 r5，所以最重要的還是遞迴式 pi + rn-i
小筆記
建表紀錄遞迴中需要重複的部分，是 DP 裡很重要的工具！