476. Stone Game

Description

There is a stone game.At the beginning of the game the player picks n piles of stones in a line.

The goal is to merge the stones in one pile observing the following rules:

At each step of the game,the player can merge two adjacent piles to a new pile.

The score is the number of stones in the new pile.

You are to determine the minimum of the total score.

Example

Example 1:

Input: [3, 4, 3]

Output: 17

Example 2:

Input: [4, 1, 1, 4]

Output: 18

Explanation:

  1. Merge second and third piles => [4, 2, 4], score = 2

  2. Merge the first two piles => [6, 4]，score = 8

  3. Merge the last two piles => [10], score = 18

思路：

1.完全使用记忆化搜索，不做优化，时间复杂度O(n3)，很难分析，最小的score是将array分成两半，然后每半边最小score加上array所有元素的和为array的最小score，然后不断递归。

2.区间动态规划.（超复杂，回头再看吧）

设定状态: f[i][j] 表示合并原序列 [i, j] 的石子的最小分数

状态转移: f[i][j] = min{f[i][k] + f[k+1][j]} + sum[i][j], sum[i][j] 表示原序列[i, j]区间的重量和

边界: f[i][i] = sum[i][i], f[i][i+1] = sum[i][i+1]

答案: f[0][n-1]

代码：

思路1：

思路2