TLE Python DP Solution O(k*m*n*m*n)


  • 0

    Short but TLE... :P

    Python Code:

    class Solution(object):
        def maxNumber(self, nums1, nums2, k):
            len1 = len(nums1)
            len2 = len(nums2)
            dp = [[[[]] * (len2 + 1) for x in range(len1 + 1)] for y in range(k + 1)]
            for z in range(1, k + 1):
                for x in range(len1 + 1):
                    for y in range(len2 + 1):
                        for p in range(x):
                            if len(dp[z-1][p][y]) == z - 1:
                                dp[z][x][y] = max(dp[z][x][y], dp[z-1][p][y]+[nums1[p]])
                        for q in range(y):
                            if len(dp[z-1][x][q]) == z - 1:
                                dp[z][x][y] = max(dp[z][x][y], dp[z-1][x][q]+[nums2[q]])
            return dp[k][len1][len2]

  • 0
    S

    May this help you
    enter link description here


Log in to reply
 

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