Relaciones de recurrencia: ¿Cuál es la suma máxima que se puede formar?

Answer 1

Las cantidades importantes aquí son el índice en el que se encuentra y el número de partidos jugados. Puede parametrizarlos y formar el siguiente estado de programación dinámica [math] dp (\ text {index}, \ text {coincidencias}) [/ math].
[math] dp (\ text {i}, \ text {m}) [/ math] es la cantidad máxima de dinero que puede ganar si está en [math] i ^ {\ text {th}} [/ math ] índice en la matriz y ya he jugado [math] m [/ math] número de partidos.

Entonces la recurrencia sigue naturalmente,

• Si excede los límites de la matriz, devuelva 0.
• Si has jugado 2 partidos, no puedes jugar el partido actual, así que devuelve dp(i + 1, 0).
• Si has jugado 1 partido, tienes una opción. Puedes jugar el partido actual o saltearlo. Entonces, dp(i, 1) = max(dp(i + 1, 0), arr[i] + dp(i + 1, 2))
• La situación por haber jugado 0 partidos es muy similar a la situación anterior.

Escribí un pseudocódigo. (jk – iz en realidad python)

def maxSum (arr, dp, i, m):
si i> = len (arr): devuelve 0
elif (i, m) en dp: return dp [(i, m)]
más:
si m == 2: dp [(i, m)] = maxSum (arr, dp, i + 1, 0)
elif m == 1: dp [(i, m)] = max (maxSum (arr, dp, i + 1, 0),
arr [i] + maxSum (arr, dp, i + 1, 2))
de lo contrario: dp [(i, m)] = max (maxSum (arr, dp, i + 1, 0),
arr [i] + maxSum (arr, dp, i + 1, 1))

No lo he probado aparte de los casos de prueba anteriores, pero creo que debería funcionar.