Could you help me with this Dynamic Programming Problem?

user_13940740 0
Viewed 141

I tried to solve the problem below using dynamic programming, but there is something wrong with my code and I could not figure it out. Could you help me with it? Thank you!

Problem: Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

Input: nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5

Output: [9, 8, 6, 5, 3]

Example 2:

Input: nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5

Output: [6, 7, 6, 0, 4]

Example 3:

Input: nums1 = [3, 9]
nums2 = [8, 9]
k = 3

Output: [9, 8, 9]

My idea is as following:

dp[i][j][t] is the the maximum number of length i which is picked out of first j digits of array 1 and first t digits of array 2, where i goes from 0 to k, j goes from 0 to len(nums1), t goes from 0 to len(nums2). the state transition equation goes like this:

  1. when nums1[j-1] > nums2[t-1]: if we already have k-2 digits, then we have to take both nums1[j-1] and nums2[t-1], and we must take nums1[j-1] first in order to maximize the result if we already have k-1 digits, then we only have to take one more digit, and it must be nums1[j-1], because it is bigger if we already have k digits, then we do not need to take more digits, so we keep the last result dp[i][j-1][t-1]

Given that we are looking for maximum, our current result should be the biggest among these 3 situations, so we have:

dp[i][j][t] = max(
    (dp[i-2][j-1][t-1]*10+nums1[j-1])*10+nums2[t-1], 
    dp[i-1][j-1][t-1]*10+nums1[j-1],
    dp[i][j-1][t-1]
)
  1. when nums1[j-1] < nums2[t-1]: if we already have k-2 digits, then we have to take both nums1[j-1] and nums2[t-1], and this time we must take nums2[t-1] first because it is bigger if we already have k-1 digits, then we only have to take one more digit, and it must be nums2[t-1], because it is bigger if we already have k digits, then we do not need to take more digits, so we keep the last result dp[i][j-1][t-1]

Likewise, we take the biggest result from these possible ones:

dp[i][j][t] = max(
    (dp[i-2][j-1][t-1]*10+nums2[t-1])*10+nums1[j-1], 
    dp[i-1][j-1][t-1]*10+nums2[t-1],
    dp[i][j-1][t-1]
)

Here is my code:

import numpy as np


def maxNumber(nums1, nums2, k):
    m = len(nums1)
    n = len(nums2)

    dp = [[[0 for _ in range(n + 1)] for _ in range(m + 1)] for _ in range(k + 1)]

    for i in range(2, k + 1):
        for j in range(i + 1):
            if j > m or (i - j) > n:
                continue
            tmp = 0
            tmp_nums1 = nums1[:j]
            tmp_nums2 = nums2[:(i-j)]

            while tmp_nums1 or tmp_nums2:
                if tmp_nums1 > tmp_nums2:
                    tmp = tmp * 10 + tmp_nums1.pop(0)
                else:
                    tmp = tmp * 10 + tmp_nums2.pop(0)
            dp[i][j][i - j] = tmp

    for i in range(m + 1):
        for j in range(n + 1):
            if not i and not j:
                continue
            dp[1][i][j] = max(nums1[:i] + nums2[:j])

    for i in range(2, k+1):
        for j in range(m+1):
            for t in range(i+1-j, n + 1):
                if nums1[j - 1] > nums2[t - 1]:
                    dp[i][j][t] = max((dp[i-2][j-1][t-1]*10+nums1[j-1])*10+nums2[t-1], dp[i][j-1][t-1], dp[i-1][j-1][t-1]*10+nums1[j-1])
                else:
                    dp[i][j][t] = max((dp[i-2][j-1][t-1]*10+nums2[t-1])*10+nums1[j-1], dp[i][j-1][t-1], dp[i-1][j-1][t-1]*10+nums2[t-1])

    # print(np.array(dp))

    res = []
    tmp_res = dp[-1][-1][-1]
    while tmp_res:
        res.append(tmp_res % 10)
        tmp_res //= 10

    return res[::-1]

But it outputs [8, 9, 9] on Example 3, and I cannot figure out the reason. Could you help me with it? Thank you in advance!

dynamic-programming algorithm python
3 Answers

Dynamic programming usually implies short-circuiting some of the computation based on results from computations made to date. Often this takes the form of a recursive function. You seem to be taking more of a brute force approach (which usually corresponds to the worse case scenario for dp)

Here is an example of a recursive approach that will lend itself better to optimization:

def largestFrom(M,N,K):
    if K == 1: return [max(M+N)]      # simple case
    if not M and len(N)==K : return N # simple case                               
    if not N and len(M)==K : return M # simple case
    result = []
    for A,B in [(N,M),(M,N)]:
        for i,a in enumerate(A):                   # trial on numbers from A
            if len(A)-i+len(B)<K: break            # can't take more from A
            if result and a < result[0]: continue  # short-circuit         
            R = [a] + largestFrom(A[i+1:],B,K-1)   # recurse with remaining numbers
            if R > result: result = R              # track best so far
    return result

After eliminating the obvious solutions that require no special processing, it goes into a recursive trial/error process that short-circuits the traversal for candidate numbers that won't improve the best result found so far.

The traversal goes through the two lists and attempts to use the number at each position as the first one in the result. It then recurses with the remaining numbers and a size of K-1. So, upon returning from the recursion, a list R is formed of the selected number followed by the largest K-1 sized suffix that can be made with the remaining numbers.

One part of the short circuiting is stopping the loop when the index of the selected number would not leave enough remaining numbers to reach a size of K-1 (i.e. combining the remainder of the current list plus all numbers of the other one).

Another part of short circuiting is comparing the number we are about to try with the first one in the best result. If the candidate number is smaller than the first one in the result, then it would be pointless to go deeper as there is no possibility to form an R list greater than the result we already have.

For example:

combining [3,9] [8,9] with K=3

  • result starts empty
  • Going through first list [3,9]
    • select 3 at position 0
      • recurse with M=[9] N=[8,9] K=2
      • will produce R = [3] + [9,8]
      • R > result, result is now [3,9,8]
    • select 9 at position 1
      • recurse with M=[] N=[8,9] K=2
      • will produce R = [9] + [8,9]
      • R > result, result is now [9,8,9]
  • Going through second list [8,9]
    • select 8 at position 0
      • 8 is smaller than R[0] (9)
      • short-circuit
    • select 9 at position 1
      • recurse with M=[3,9] N=[] K=2
      • will produce R = [9] + [3,9]
      • result unchanged (R is < result)
  • return result [9,8,9]

The for A,B in [(N,M),(M,N)]: loop is merely a shorthand way to avoid duplicating the code for the trial loops on numbers in M and numbers N.

testSet = [ ([3,4,6,5],[9,1,2,5,8,3],5),
            ([6, 7], [6, 0, 4],5),
            ([3, 9], [8, 9],3)
          ]

for M,N,K in testSet:
    print(M,N,K,":",largestFrom(M,N,K))


[3, 4, 6, 5] [9, 1, 2, 5, 8, 3] 5 : [9, 8, 6, 5, 3]
[6, 7] [6, 0, 4] 5 : [6, 7, 6, 0, 4]
[3, 9] [8, 9] 3 : [9, 8, 9]
user_52375600

There is alternative way than DP to solve it. Here I've just crafted another solution:

def maxNumber(nums1, nums2, k):

    def pick(nums, k):
        stack = []
        drop = len(nums) - k
        
        for num in nums:
            while drop and stack and stack[-1] < num:
                stack.pop()
                drop -= 1
            stack.append(num)
        return stack[:k]

    def merge(A, B):
        ans = []
        while A or B:
            bigger = A if A > B else B
            ans.append(bigger.pop(0))
        return ans

    return max(merge(pick(nums1, i), pick(nums2, k-i))
               for i in range(k+1) if i <= len(nums1) and k-i <= len(nums2))

if __name__ == '__main__':
    nums1 = [3, 4, 6, 5]
    nums2 = [9, 1, 2, 5, 8, 3]

    print(maxNumber(nums1, nums2, 5))
    print(maxNumber([3,9],[8,9], 3))
user_107607680

Are those answers to your examples provided by the professor? Because they don't make sense to me. Surely the largest number is one that uses all of the digits available? i.e. the largest value will always mean k=m+n. You can't possibly have a larger answer with k=m+(n-1) for instance. What am I missing?

Example 3:
Input: nums1 = [3, 9]  
nums2 = [8, 9]  
k = 3  
Output: [9, 8, 9]  
or - in my world  k = 4 / Output: [8, 9, 3, 9]

(Hmm... I guess they were provided. Seems a weird question to me. Sorry - I'm unable to help, but I'll post this anyway in case someone else wonders the same thing I did. To me the hard part would be to actually work out what the largest number would be, using all digits. But even then that's not that hard: Compare positions 1 - use the value from the larger array. Compare position 1 of the non-chosen array with position 2... and so on.)

user_114806500
Related