https://articles.leetcode.com/the-painters-partition-problem-part-ii/
递归：
image.png
O(KN3)
dp
https://www.geeksforgeeks.org/painters-partition-problem/
O(KN**2)
import sys
def findMax(arr, n, k):
if not arr:
return 0
dp = [[0 for col in range(n + 1)] for row in range(k + 1)]
for i in range(1, n + 1):
dp[1][i] = sum(arr[0:i])
for i in range(1, k + 1):
dp[i][1] = arr[0]
for i in range(2, k + 1):
for j in range(2, n + 1):
_min = sys.maxsize #maxint python2
for p in range(1, j + 1):
_min = min(_min, max(dp[i - 1][p], sum(arr[p:j])))
dp[i][j] = _min
return dp[k][n]
def test():
arr = [10, 20, 30, 40,50,60]
k = 3
print(findMax(arr, len(arr), k))
if __name__ == '__main__':
test()
binary search
https://www.geeksforgeeks.org/painters-partition-problem-set-2/
