出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944
解題策略
cost[x][y]記錄x到y的最小cost，不重複求取，若計算過就直接回傳，
有關係為cost[left][right]=min(cost[left][right],dp(left,cut[i])+dp(cut[i],right)+right-left)，
cut[i]為介於left與right的所有點，
cost[][]先初始化為很大的值 ，
cost[x][y]中間沒有cut，cost[x][y]=0‧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
/*cost[x][y]記錄x到y的最小cost，不重複求取，若計算過就直接回傳， 有關係為cost[left][right]=min(cost[left][right],dp(left,cut[i])+dp(cut[i],right)+right-left)， cut[i]為介於left與right的所有點， cost[][]先初始化為很大的值 ， cost[x][y]中間沒有cut，cost[x][y]=0‧ */#include <iostream>#include <algorithm>#define MAXL 1005#define MAXINT 0x7fffffffusing namespace std; int cost[MAXL][MAXL],cut[52],len,n; int min(int x,int y){ if (x>y) return y; else return x; } int dp(int left,int right){ bool found=false; if (cost[left][right] != MAXINT) return cost[left][right]; for(int i=0;i<n;i++){ if ((cut[i]>left)&&(cut[i]<right)) { found=true; cost[left][right]=min(cost[left][right],dp(left,cut[i])+dp(cut[i],right)+right-left); } } if (found==false) cost[left][right]=0; return cost[left][right]; } int main(){ int result; while (cin >> len){ if (len == 0) break; cin >> n; for(int i=0;i<n;i++){ cin >> cut[i]; } for(int i=0;i<=len;i++) for(int j=0;j<=len;j++) cost[i][j]=MAXINT; result=dp(0,len); cout << "The minimum cutting is " << result << "." << endl; } return 0; }