Нахождение максимальной суммы путем удаления элементов из заголовка или конца списка с добавленной стоимостью в зависимости от порядка их удаления

Question

Нам дан список L целых чисел вместе со списком K целых чисел. Цель состоит в том, чтобы максимизировать сумму с помощью ограничения, чтобы удалить по одному элементу за раз из начала или конца списка L, и этот элемент будет умножен на значение K [i] (при условии, что i - это порядок удаления) ,

Эта процедура будет go продолжаться до тех пор, пока мы не используем все значения списка K.

Один из примеров:

L = [5,11,2,3,22,1]    
K = [1,3,2]

Оптимальное решение вернет сумму 1*1 + 3*22 + 2*5.

Я думаю об использовании динамического программирования c и рассмотрении массива dp[i][j], который вернул бы максимальную сумму для списка L[i:j+1]. Таким образом, я мог думать о повторении как:

dp[i][j] = max(dp[i+1][j] + L[i] * (?), dp[i][j-1] + L[j] * (?))  

Хотя я не уверен, как я мог бы заполнить эти вопросительные знаки и как заполнить массив, чтобы получить ответ dp[0][n].

Answer 1

Одно из возможных решений:

L = [5,11,2,3,22,1]
K = [1,3,2]

def solution(L, K):
    if len(K) == 0:
        return 0

    sol1 = K[0] * L[0] + solution(L[1:], K[1:])
    sol2 = K[0] * L[-1] + solution(L[:-1], K[1:])

    return max(sol1, sol2)

print(solution(L, K))

Отпечатки:

77

---

Если вы хотите увидеть, что было умножено, вы можете попробовать это:

def solution(L, K):
    if len(K) == 0:
        return 0, []

    s1, p1 = solution(L[1:], K[1:])
    s2, p2 = solution(L[:-1], K[1:])

    sol1 = K[0] * L[0] + s1
    sol2 = K[0] * L[-1] + s2

    if sol1 > sol2:
        return sol1, p1 + [(K[0], L[0])]
    else:
        return sol2, p2 + [(K[0], L[-1])]


print(solution(L, K))

Это печатает:

(77, [(2, 5), (3, 22), (1, 1)])