問題描述 　　在一條直線上有n堆石子，每堆有一定的數(shù)量，每次可以將兩堆相鄰的石子合并，合并后放在兩堆的中間位置，合并的費用為兩堆石子的總數(shù)。求把所有石子合并成一堆的最小花費。 輸入格式 　　輸入第一行包含一個整數(shù)n，表示石子的堆數(shù)。
　　接下來一行，包含n個整數(shù)，按順序給出每堆石子的大小 。 輸出格式 　　輸出一個整數(shù)，表示合并的最小花費。 樣例輸入 5
1 2 3 4 5 樣例輸出 33 數(shù)據(jù)規(guī)模和約定 　　1<=n<=1000, 每堆石子至少1顆，最多10000顆。 題目分析 　　這是一道很經(jīng)典的動態(tài)規(guī)劃題（據(jù)說），但是我不會，哈哈哈。我的理解是，逆向考慮這個題，把一堆石頭分為兩堆。 　　因此，設(shè)置一個中間點k ，d[ i ][ j ] = min(d[ i ][ n ], d[ 1 ][ k ] + d[k + 1][ j ])，遍歷每一個處于[ i , j ]中的每一個中間點k 遞歸實現(xiàn)的話，最后一個樣例會超時。 int dp(int i, int j) {if (d[i][j] || i==j) return d[i][j];int mi = bigdata;for (int ii = i; ii < j; ii++) {int t = dp(i, ii) + dp(ii + 1, j);if(mi > t) mi = t;}return d[i][j] = mi + sum[j] - sum[i - 1]; }

循環(huán)實現(xiàn)

for (int i = n - 1; i > 0; i--) {//起點for (int j = i + 1; j <= n; j++) {//終點long long t = bigdata;for (int k = i; k < j; k++) {//中間點long long temp = d[i][k] + d[k + 1][j];if (t > temp) t = temp;}d[i][j] = t + sum[j] - sum[i - 1];}}

?

轉(zhuǎn)載于:https://www.cnblogs.com/woxiaosade/p/10455677.html

總結(jié)

以上是生活随笔為你收集整理的算法提高 合并石子【动态规划】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。