動態規劃DP

NYOJ 石子合併(一)經典區間DP

石子合併(一) 時間限制:1000 ms  |  記憶體限制:65535 KB 難度:3 描述     有N堆石子排成一排,每堆石子有一定的數量。現要將N堆石子併成為一堆。合併的過程只能每次將相鄰的兩堆石子堆成一堆,每次合併花費的代價為這兩堆石子的和,經過N-1次合併後成為一堆。求出總的代價最小值。 […]

石子合併問題3種題型

石子合併問題是最經典的DP問題。首先它有如下3種題型: (1)有N堆石子,現要將石子有序的合併成一堆,規定如下:每次只能移動任意的2堆石子合併,合併花費為新合成的一堆石子的數量。求將這N堆石子合併成一堆的總花費最小(或最大)。 分析:當然這種情況是最簡單的情況,合併的是任意兩堆,直接貪心即可,每次選 […]