painter-partition-problem

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/