Python | Easy to understand | Greedy + Dynamic Programminng
To solve the problem, we can define the subproblem "getMaxNumberString(i, j, length)": get the max number string with "length" from index "i" in nums1 and index
To solve the problem, we can define the subproblem "getMaxNumberString(i, j, length)": get the max number string with "length" from index "i" in nums1 and index "j" in nums2.\n\ngetMaxNumberString(i, j, length)\n- if nums1 has bigger digit, getMaxNumberString(i, j, length) = str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1)\n- if nums2 has bigger digit, getMaxNumberString(i, j, length) = str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1)\n- if nums1 and nums2 have the same big digit, getMaxNumberString(i, j, length) = max(str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1),  str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1))\n\n```\nclass Solution:\n    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:\n        m = len(nums1)\n        n = len(nums2)\n        dp = {}\n        \n        # get the max number string with "length" from index "i" in nums1 and index "j" in nums2\n        # using number string to easy to compare\n        def getMaxNumberString(i, j, length):\n            if length == 0:\n                return ""\n            \n            # using memoization to optimize for the overlapping subproblems\n            key = (i, j, length)\n            if key in dp:\n                return dp[key]\n            \n            # greedy to find the possible max digit from nums1 and nums2\n            # 1) bigger digit in the higher position of the number will get bigger number\n            # 2) at the same time, we need to ensure that we still have enough digits to form a number with "length" digits\n            \n            # try to find the possible max digit from index i in nums1\n            index1 = None\n            for ii in range(i, m):\n                if (m - ii + n - j) < length:\n                    break\n                if index1 is None or nums1[index1] < nums1[ii]:\n                    index1 = ii\n            \n            # try to find the possible max digit from index j in nums2\n            index2 = None\n            for jj in range(j, n):\n                if (m - i + n - jj) < length:\n                    break\n                if index2 is None or nums2[index2] < nums2[jj]:\n                    index2 = jj\n                    \n            maxNumberStr = None\n            if index1 is not None and index2 is not None:\n                if nums1[index1] > nums2[index2]:\n                    maxNumberStr = str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1)\n                elif nums1[index1] < nums2[index2]:\n                    maxNumberStr = str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1)\n                else:\n                    # get the same digit from nums1 and nums2, so need to try two cases and get the max one \n                    maxNumberStr = max(str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1), str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1))\n            elif index1 is not None:\n                maxNumberStr = str(nums1[index1]) + getMaxNumberString(index1 + 1, j, length - 1)\n            elif index2 is not None:\n                maxNumberStr = str(nums2[index2]) + getMaxNumberString(i, index2 + 1, length - 1)\n            \n            dp[key] = maxNumberStr\n            return maxNumberStr\n\n        result_str = getMaxNumberString(0, 0, k)\n        \n        # number string to digit array\n        result = []\n        for c in result_str:\n            result.append(int(c))\n        \n        return result\n```
['Dynamic Programming', 'Greedy', 'Python3']