DP Python TLE O(k*n^3)


  • 0
    W
    class Solution(object):
        def maxProfit(self, k, prices):
            """
            :type k: int
            :type prices: List[int]
            :rtype: int
            """
            n=len(prices)
            if n<=1 or k==0:
                return 0
            prof=[[[0 for i in range(k+1)] for j in range(n)] for m in range(n)]
            for i in range(n-1):
                min_p=prices[i]
                max_p=0
                for j in range(i+1,n):
                    min_p=min(min_p,prices[j])
                    max_p=max(max_p,prices[j]-min_p)
                    prof[i][j][1]=max_p
                
            for m in range(2,k+1):
                for incr in range(2,n):
                    for i in range(n-incr):
                        j=i+incr
                        re=prof[i][j][m-1]
                        for cut in range(i+1,j-1):
                            re=max(re,prof[i][cut][1]+prof[cut+1][j][m-1])
                        prof[i][j][m]=re
            return prof[0][n-1][k]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.