Leetcode - 每周游戏 388

划分dp

定义 f [ i ][ j ] 表示将前 j 个数分成 i 段所得到的最大值

根据题目要求，f [ i ] [ j ] 的转移来源有两个：

1. 不选择当前数，那么f[ i ][ j ]可以等价于将前 j - 1 个数分成 i 段所得到的最大值， 即 f [ i ][ j-1 ]
2. 选择当前数，设选择的子数组的范围是[L，j）该子数组的和为 pre[ j ] - pre[ L ]，那么当前的转移方程是 f [i - 1][ L ] + (k-i+1) * (-1)^(i+1) * (pre[ j ]- pre[ L ] )

可以得到如下的递推方程：

f [ i ][ j ] = Math.max( f [ i ][ j - 1]，f [i - 1][ L ] + (k-i+1) * (-1)^(i+1) * (pre[ j ]- pre[ L ] ) )

可以看出来，如果要计算上述 f [ i ][ j ]，需要遍历三个未知数 i ，j，L，这样的话就会超时，所以还要优化。可以将上述的方程因式分解：

设 w = (-1)^(i+1)

f [ i ][ j ] = Math.max( f [ i ][ j - 1]，f [i - 1][ L ] + w * (pre[ j ] - pre[ L ] ) )

              = Math.max( f [ i ][ j - 1]，f [i - 1][ L ] - w * pre[ L ] + w * pre[ j ] )

可以看出只有 mx =  f [i - 1][ L ] - w * pre[ L ] 与 L 有关系，能否将 L 这层循环省略：

当 j = i 时，计算 L = { i - 1 } 

当 j = i+1时，计算 L = { i - 1，i }

当 j = i+2时，计算 L = { i - 1，i，i + 1 }

.....

可以看出 L 除了等于 j-1时没有重复计算，其他情况一直在重复计算，通过这一特点，就可以将L这层循环给省略掉了。

注：i <= j，因为要将 j 个数分成 i 段，那么至少也要有 i 个数