593. Stone Game II

593. Stone Game II 区间型动态规划

在 Stone Game 之一的基础上, A 是一个环形数组, 尝试每一个断点, 将环断开.

way 1, 实现: A 数组 double, 即 A.append(A),
(DP) f 数组从 n 延长到 2n, 计算每一段长度为 n 的子数组的最少组合, 相当于尝试每一个断点, 取结果最小的一段.
计算顺序: length in 0..n, length 和之一一样, 最长到 n.

最后一步: min(左半边 + 右半边, 尝试每种拆分 分组, mid in l..r) + 子数组和.
子问题, f[l][r] = Min (mid in l..r) (f[l][mid] + f[mid+1][r]) + sum(A[l:r+1])
初始化:
f[l][r] = 0
计算顺序:
length (ln) in 1..n:
- l in 0..n-length:
- r = l + length;

f[][] 当中, i in 0..n-1: 取 f[i][i+n-1] 值最小的一个.

<code>
class Solution:
    def stoneGame2(self, A):
        if not A:
            return 0
        # init
        n = len(A)
        A.extend(A)

        f = [[float("inf")] * (2*n) for _ in range(2*n)]

        for ln in range(0,n):
            for l in range(2*n - ln):
                r = l + ln
                if ln == 0:
                    f[l][r] = 0
                    continue
                # if ln == 1:
                #     f[l][r] = A[l] + A[r]
                #     continue
                for k in range(l, r):
                    f[l][r] = min(f[l][r], f[l][k] + f[k+1][r])
                f[l][r] += sum(A[l:r+1])

        ans = float("inf")
        for l in range(0, n):
            ans = min(ans, f[l][l + n - 1])
        return ans

A = [1, 1, 1, 1]
# Output:8