1、問題

( 1 )路邊玩法
有 n 堆石子堆放在路邊,現要將石子有序地合并成一堆,規定每次只能移動相鄰的兩堆石子合并,合并花費為新合成的一堆石子的數量。求將這 N 堆石子合并成一堆的總花費(最小或最大)。

 

 

 

2、分析

( 1 )建立最優值遞歸式
設 Min [i][j] 代表從第 i 堆石子到第 j 堆石子合并的最小花費, Min [i][k] 代表從第 i 堆石子到第 k 堆石子合并的最小花費,Min[k+1][j] 代表從第 k+1 堆石子到第 j 堆石子合并的最小花費, w ( i , j )代表從 i 堆到 j 堆的石子數量之和。列出遞歸式:
Min [ i ][ j ] = 0 （i = j）
Min [ i ][ j ] = min ( Min [ i ][ k ] + Min [ k + 1][ j ] + w ( i , j )) , i < j（ i ≤ k < j）
Max [i][j] 代表從第 i 堆石子到第 j 堆石子合并的最大花費,Max [i][k] 代表從第 i 堆
石子到第 k 堆石子合并的最大花費,Max [k+1][j] 代表從第 k+1 堆石子到第 j 堆石子合并的最大花費, w ( i , j )代表從 i 堆到 j 堆的石子數量之和。列出遞歸式:

Max [ i ][ j ] = 0 （i = j）
Max [ i ][ j ] =max( Max [ i ][ k ] + Max [ k + 1][ j ] + w ( i , j )) , i < j

總結

以上是生活随笔為你收集整理的动态规划之石子合并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。