10003 - Cutting Sticks（DP）

類似于最優矩陣鍊乘，将長區間劃分成段區間求解，換句話說：長區間依賴于段區間 。 是以如果利用三重循環遞推的話，枚舉的順序應該是木棍的長度從小到大，因為長區間依賴于短區間的最優解 。 是以動态規劃的重點我認為就是對狀态的定義和動态規劃的方向，  狀态的定義要確定覆寫所有狀态，規劃的方向要遵循一個狀态依賴于另一個早已解決的狀态。     是以該題有兩種解決方法：記憶化搜尋和遞推 。

我分别用這兩種方法AC了，記憶化搜尋更簡單易想，耗時0.339。但是遞推更快！耗時0.086 。細節請見代碼：

1.記憶化搜尋：

#include<bits/stdc++.h>
using namespace std;
const int INF = 2000000000;
int n,l,a[55],d[55][55];
int dp(int i,int j) {
    int& ans = d[i][j];
    if(ans!=-1) return ans;
    ans = INF;
    for(int k=i+1;k<j;k++) {
        ans = min(ans,dp(i,k) + dp(k,j) + a[j] - a[i]);
    }
    return ans;
}
int main() {
    while(~scanf("%d",&l)&&l) {
        scanf("%d",&n);
        memset(d,-1,sizeof(d));//初始化特殊值
        for(int i=0;i<=n;i++) d[i][i+1] = 0; //初始化邊界
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        a[n+1] = l; a[0] = 0;
        printf("The minimum cutting is %d.\n",dp(0,n+1));
    }
    return 0;
}
           

2.遞推：

#include<bits/stdc++.h>
using namespace std;
const int INF = 2000000000;
int n,l,a[55],d[55][55];
int main() {
    while(~scanf("%d",&l)&&l) {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        a[n+1] = l; a[0] = 0;
        for(int len=1;len<=n+1;len++) { //按照木棍長度從小到大遞推
            for(int i=0;i<=n;i++) {//i + len 就是j
                if(i+len > n+1) break;
                d[i][i+len] = (len == 1 ? 0 : INF);
                for(int k=i+1;k<i+len;k++) { //尋找切割點
                    d[i][i+len] = min(d[i][i+len],d[i][k] + d[k][i+len] + a[i+len] - a[i]);
                }
            }
        }
        printf("The minimum cutting is %d.\n",d[0][n+1]);
    }
    return 0;
}