LC1388 3n 块披萨

环形 DP 求最大值。

题目可以转化为：在一个大小为 \(3n\) 的环上选取互不相邻的 \(n\) 个数，使其和最大。

这个问题如果在链上，显然可以通过 DP 解决。设 \(dp_{i,j}\) 表示截止到 \(i\)，选取了 \(j\) 个数的最大值，可以写出转移方程：\(dp_{i,j}=\max(dp_{i-1,j}, dp_{i-2,j-2}+slices_i)\)。

初始化：因为是求最大值，将 DP 数组初值设为 \(-\infty\)，因为涉及到 \(i-2\)，所以要预先设置 \(i=0,i=1\) 的情况。

现在问题是在环上，对于环形 DP 有两种解决方法：破环为链和两次 DP。前者方便循环取用原数组，后者方便处理 DP 数组。观察式子可知本题使用两次 DP 法：如果选取了第一块，则最后一块不会选取；如果选取了最后一块，则第一块不会选取。所以一次去头、一次去尾（保证选不到头或者尾），DP 两次，取两次的最大值作为答案。

AC 代码：

func calculate(slices []int) int {
    N, n := len(slices), (len(slices) + 1) / 3 //这里的数组长度变成了3n-1
    dp := make([][]int, N)
    for i := 0; i < N; i++ {
        dp[i] = make([]int, n + 1)
        for j := 1; j <= n; j++ {
            dp[i][j] = -0x3f3f3f3f
        }
    }
    dp[0][0], dp[1][0], dp[0][1], dp[1][1] = 0, 0, slices[0], max(slices[0], slices[1])
    for i := 2; i < N; i++ {
        dp[i][0] = 0
        for j := 1; j <= n; j++ {
            dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i])
        }
    }
    return dp[N - 1][n]
}

func maxSizeSlices(slices []int) int {
    return max(calculate(slices[1:]), calculate(slices[:len(slices) - 1]))
}

几点收获：

1. 积极主动地把题目情景转化为数学语言描述；
2. 两种环形 DP 的思路。