UVA 10003 Cutting Sticks (DP)

DP = Dynamic Programming, 動態規劃


#思考

假設今天有一條木頭，長100

要切的位置有三個點：25, 50, 75




切割點

0

1

2

3

4


刻度

0

25

50

75

100






把木頭的兩個端點也考慮進去

題目問最小的花費(cost)

我們可以把花費當作把木頭搬上切割的工作台需要的成本(恰等於木頭長度)

木頭越長，要付給木工的錢就越多









*先假設一種情況：

把100的木頭搬上工作台，cost = 100

先在50的位置切下，剩下0到50，50到100兩段木頭

把0到50的木頭搬上，cost加上50，再切25的位置，半段木頭完成切割

50到100也一樣，搬上去，cost加50，再切75，半段完成

所以，依照這樣的切割流程，總花費是100+50+50=200


以此類推，也可以先切25，再切75，再切50，etc

三個切割點共有3! =6種排列

但問題是，我們不可能真的每一種排列都去嘗試，那樣太沒效率

這時候要使用DP


但問題是，我們怎麼知道這題要用DP解？









#DP的主要構成元素有二：

1. Optimal Substructure(最優子結構)：



    大問題可以分解成小問題，小問題可以再分解成小小問題...直到最小的問題可以直接算出來，再逆推得到大問題的答案。

    其實這也就是分治法(Divide and Conquer)啦！

2. Overlapping Subproblem(重覆子問題):

    有很多重複的小問題









*怎麼看出這題切木頭有最優子結構？


可以這樣想：

長100的木頭，可以看成兩段50的木頭

這兩段50的木頭分別做切割，可以找到最小花費

50的木頭可以再看成兩段25的木頭，0到25、25到50

但是25的木頭不能再切割了，所以花費是0

所以切割長度50的木頭，你只需花費搬上工作台的成本50

兩段50的木頭，cost = 50+50

(另一段同理，50到75、75到100，一樣都不能再切割)

別忘了還有搬上100木頭的成本100

你看，花費的加總不正是這個切割情況下的答案嗎？


當然，這是先切50的情形，其他情況也是以此類推

從這個角度來看，最優子結構已經浮出表面了









*那重複子問題呢？


那就這樣想：

先切75，就看成0到75跟75到100

75到100不能再切

0到75如果先切50，可以看成0到50跟50到75兩段木頭

發現了嗎？小問題重複了！







DP的精髓就在於此：

因為有很多重複的小問題

如果每次都重新算過一遍，那跟所有排列都算過一遍根本沒什麼不一樣

但如果，每一次算出小問題的答案就把它記錄下來

下次再遇到有需要計算那個小問題的答案時只要查表，就可以直接拿來用

效率不就大大提升了嗎











好，所以我們現在已經知道，這題用DP來解是個好主意

那怎麼寫才能把所有情形都跑過一次呢？











先令木頭長度為l(length)，切割點數量n

cost建表為dp[n][n](n最大不超過50，可直接設成dp[52][52])，比如dp[0][2]，紀錄的就是0到50的最小花費

table紀錄每個切割點的刻度，這樣才方便計算未切割前搬上工作台要花的cost

r(range)是區間範圍，b(begin)是起始點，e(end)是終點







#include <iostream>
#include <climits>
using namespace std;

int main(int argc, const char * argv[]) {
    int l, n;
    while (cin >> l && l != 0) {
        cin >> n;
        int dp[52][52] = {0};
        int *table = new int[n+2];
        n++;
        table[0] = 0; table[n] = l;
        for (int i = 1; i < n; i++) cin >> table[i];
        int r, b, e, c, temp;
        for (r = 2; r <= n; r++) {
            for (b = 0; b < n; b++) {
                e = b + r;
                if (e > n) break;
                dp[b][e] = INT_MAX;
                for (c = b+1; c < e; c++) {
                    temp = dp[b][c] + dp[c][e] + table[e] - table[b];
                    if (temp < dp[b][e]) dp[b][e] = temp;
                }
                
            }
        }
        printf("The minimum cutting is %d.\n", dp[0][n]);
    }
    return 0;
}
}


程式碼看起來還是很抽象。
但你可以按部就班、土法煉鋼的去理解它----跟著程式碼一步一步走，看它怎麼走的
ex前面的例子:長100的木頭

像這樣一步一步去觀察

每一次temp算出來的答案如果小於紀錄值，dp就會被temp取代

r從2開始的原因在於，r=1時，所有cost都等於0(因為不用切)

之後你會發現，這個code的DP是使用Bottom-Top:

從最小區間開始填，大的區間會用到小區間的答案

之後再來補充Top-Bottom的解法