Блог

Я пытался решить проблему ниже, используя динамическое программирование, но что-то не так с моим кодом, и я не мог понять это. Не могли бы вы помочь мне с этим? Спасибо!

Проблема: даны два массива длиной m и n с цифрами 0-9, представляющими два числа. Создайте максимальное число длины k <= m n из двух цифр. Относительный порядок цифр из одного и того же массива должен быть сохранен. Возвращает массив из k цифр.

Примечание: вы должны попытаться оптимизировать свою временную и пространственную сложность.

Пример 1:

Ввод: nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5

Вывод: [9, 8, 6, 5, 3]

Пример 2:

Ввод: nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5

Вывод: [6, 7, 6, 0, 4]

Пример 3:

Ввод: nums1 = [3, 9]
nums2 = [8, 9]
k = 3

Вывод: [9, 8, 9]

Моя идея заключается в следующем:

dp[i][j][t] это максимальное число длины i, которое выбирается из первых j цифр массива 1 и первых t цифр массива 2, где i идет от 0 к k , j идет от 0 к len(nums1) , t идет от 0 к len(nums2) . уравнение перехода состояния выглядит следующим образом:

1. когда nums1[j-1] > nums2[t-1] : если у нас уже есть k-2 цифры, тогда мы должны взять оба nums1[j-1] и nums2[t-1] , и мы должны взять nums1[j-1] сначала, чтобы максимизировать результат, если у нас уже есть k-1 цифры, тогда нам нужно взять только еще одну цифру, и она должна быть nums1[j-1] , потому что она больше, если у нас уже есть k цифры, тогда мы не нужно брать больше цифр, поэтому мы сохраняем последний результат dp[i][j-1][t-1]

Учитывая, что мы ищем максимум, наш текущий результат должен быть самым большим среди этих 3 ситуаций, поэтому мы имеем:

 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]
)
 

2. когда nums1[j-1] < nums2[t-1] :
   если у нас уже есть k-2 цифры, то мы должны взять оба nums1[j-1] и nums2[t-1] , и на этот раз мы должны взять nums2[t-1] первый, потому что он больше,
   если у нас уже есть k-1 цифры, тогда нам нужно взять только еще одну цифру, и она должна быть nums2[t-1] , потому что она больше
   , если у нас уже есть k цифры, тогда мы ненужно взять больше цифр, поэтому мы сохраняем последний результат dp[i][j-1][t-1]

Аналогично, мы получаем наибольший результат из этих возможных:

 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]
)
 

Вот мой код:

 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]
 

Но он выводится [8, 9, 9] в примере 3, и я не могу понять причину. Не могли бы вы помочь мне с этим?
Заранее благодарю вас!

Динамическое программирование обычно подразумевает короткое замыкание некоторых вычислений на основе результатов вычислений, выполненных на сегодняшний день. Часто это принимает форму рекурсивной функции. Похоже, вы больше придерживаетесь подхода грубой силы (что обычно соответствует худшему сценарию для dp).

Вот пример рекурсивного подхода, который лучше подходит для оптимизации:

 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
                  
 

После устранения очевидных решений, которые не требуют специальной обработки, он переходит в рекурсивный процесс проб / ошибок, который замыкает обход для чисел кандидатов, которые не улучшат лучший результат, найденный до сих пор.

Обход проходит через два списка и пытается использовать число в каждой позиции в качестве первого в результате. Затем он повторяется с оставшимися числами и размером K-1. Итак, по возвращении из рекурсии формируется список R из выбранного числа, за которым следует суффикс наибольшего размера K-1, который может быть создан с оставшимися числами.

Одна часть короткого замыкания останавливает цикл, когда индекс выбранного числа не оставляет достаточного количества оставшихся чисел для достижения размера K-1 (т. Е. Объединение оставшейся части текущего списка плюс все номера другого).

Другая часть короткого замыкания заключается в сравнении числа, которое мы собираемся попробовать, с первым в лучшем результате. Если число кандидатов меньше первого в результате, то было бы бессмысленно углубляться, поскольку нет возможности сформировать список R, больший, чем результат, который у нас уже есть.

Например:

объединение [3,9] [8,9] с K =3

• результат начинается с пустого
• Просмотр первого списка [3,9]
  • выберите 3 в позиции 0
    • рекурсия с M=[9] N= [8,9] K= 2
    • произведет R = [3] [9,8]
    • R> результат, результат теперь [3,9,8]
  • выберите 9 в позиции 1
    • рекурсия с M=[] N= [8,9] K= 2
    • произведет R = [9] [8,9]
    • R > результат, результат теперь равен [9,8,9]
• Просмотр второго списка [8,9]
  • выберите 8 в позиции 0
    • 8 меньше, чем R[0] (9)
    • короткое замыкание
  • выберите 9 в позиции 1
    • рекурсия с M=[3,9] N=[] K= 2
    • произведет R = [9] [3,9]
    • результат без изменений (R — <результат)
• возвращаемый результат [9,8,9]

for A,B in [(N,M),(M,N)]: Цикл — это просто сокращенный способ избежать дублирования кода для пробных циклов с числами в M и числами 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]
 

Для ее решения есть альтернативный способ, отличный от DP. Здесь я только что создал другое решение:

 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))
 

Эти ответы на ваши примеры предоставлены профессором? Потому что они не имеют смысла для меня. Конечно, наибольшее число — это число, в котором используются все доступные цифры? т. Е. Наибольшее значение всегда будет означать k = m n . У вас не может быть большего ответа, например, с k = m (n-1) . Чего мне не хватает?

 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]
 

(Хм… Я думаю, они были предоставлены. Мне кажется странным вопрос. Извините — я не могу помочь, но я все равно опубликую это на случай, если кто-то еще задастся вопросом о том же, что и я. Для меня самой сложной частью было бы определить, каким будет наибольшее число, используя все цифры. Но даже тогда это не так сложно: сравните позиции 1 — используйте значение из большего массива. Сравните позицию 1 невыбранного массива с позицией 2 … и так далее.)