Estrategia óptima para un Juego con modificaciones

Declaración del problema : Considere una fila de n monedas de valores v1. . . vn, donde n es par. Jugamos un juego contra un oponente alternando turnos. En cada turno, un jugador realiza la siguiente operación K veces .
El jugador selecciona la primera o la última moneda de la fila, la elimina de la fila de forma permanente y recibe el valor de la moneda.
Determine la cantidad máxima posible de dinero que el usuario definitivamente puede ganar si el usuario se mueve primero.
Nota: el oponente es tan inteligente como el usuario.
Ejemplos: 
 

Entrada: array = {10, 15, 20, 9, 2, 5}, k=2 
Salida: 32 
Explicación: 
Digamos que el usuario eligió inicialmente 10 y 15. 
El valor de las monedas que tiene el usuario es 25 y 
{20 , 9, 2, 5} quedan en la array. 
En la segunda ronda, el oponente elige 20 y 9, lo que hace que su valor sea 29. 
En la tercera ronda, el usuario elige 2 y 5, lo que hace que su valor total sea 32. 
Entrada: array = {10, 15, 20, 9, 2} , k=1 
Salida: 32 
 

Enfoque: 
se debe formar una solución recursiva y se deben almacenar los valores de los subproblemas para calcular el resultado. 
Tomando un ejemplo para llegar a la solución recursiva;
arr = {10, 15, 20, 9, 2, 5}, k=2 
Entonces, si el usuario selecciona 10, 15 en el primer turno, quedan 20, 9, 2, 5 en la array. 
Pero si el usuario selecciona 10, 5; luego quedan 15, 20, 9, 2 en la array. 
Por último, si el usuario selecciona 5, 2; luego quedan 10, 15, 20, 9 en la array.
Entonces, en cualquier iteración después de seleccionar k elementos, queda un subarreglo continuo de longitud nk para el próximo cálculo.
Entonces se puede formar una solución recursiva donde: 
 

S(l, r) = (suma(l, r) – suma(l+i, l+i+nk-1))+(suma(l+i, l+i+nk-1) – S(l +i, l+i+nk-1)) 
donde l+i+nk-1<=r 
 

Suma de los elementos elegidos Sc=(sum(l, r) – sum(l+i, l+i+nk-1)) 
Ahora el oponente realizará el siguiente turno, por lo que la 
Suma de los elementos elegidos en los próximos pasos = la suma total de los presentes array de l a r: 
suma de elementos elegidos por el oponente en los próximos pasos que es igual a 
 

Nc=(sum(l+i, l+i+n-k-1) - S(l+i, l+i+n-k-1)).
S(l, r) = Sc + Nc
where,
Nc=(sum(l+i, l+i+n-k-1) - S(l+i, l+i+n-k-1))
Sc=(sum(l, r) - sum(l+i, l+i+n-k-1))

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return sum of subarray from l to r
ll sum(int arr[], int l, int r)
{
    // calculate sum by a loop from l to r
    ll s = 0;
    for (int i = l; i <= r; i++) {
        s += arr[i];
    }
    return s;
}
 
// dp to store the values of sub problems
ll dp[101][101][101] = { 0 };
 
ll solve(int arr[], int l, int r, int k)
{
    // if length of the array is less than k
    // return the sum
    if (r - l + 1 <= k)
        return sum(arr, l, r);
 
    // if the value is previously calculated
    if (dp[l][r][k])
        return dp[l][r][k];
 
    // else calculate the value
    ll sum_ = sum(arr, l, r);
    ll len_r = (r - l + 1) - k;
    ll len = (r - l + 1);
    ll ans = 0;
 
    // select all the sub array of length len_r
    for (int i = 0; i < len - len_r + 1; i++) {
        // get the sum of that sub array
        ll sum_sub = sum(arr, i + l, i + l + len_r - 1);
 
        // check if it is the maximum or not
        ans = max(ans, (sum_ - sum_sub) + (sum_sub -
                  solve(arr, i + l, i + l + len_r - 1, k)));
    }
 
    // store it in the table
    dp[l][r][k] = ans;
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 10, 15, 20, 9, 2, 5 }, k = 2;
    int n = sizeof(arr) / sizeof(int);
    memset(dp, 0, sizeof(dp));
 
    cout << solve(arr, 0, n - 1, k);
 
    return 0;
}

// Java implementation of the above approach
class GFG
{
     
    // Function to return sum of subarray from l to r
    static int sum(int arr[], int l, int r)
    {
        // calculate sum by a loop from l to r
        int s = 0;
        for (int i = l; i <= r; i++)
        {
            s += arr[i];
        }
        return s;
    }
     
    // dp to store the values of sub problems
    static int dp[][][] = new int[101][101][101] ;
     
    static int solve(int arr[], int l, int r, int k)
    {
        // if length of the array is less than k
        // return the sum
        if (r - l + 1 <= k)
            return sum(arr, l, r);
     
        // if the value is previously calculated
        if (dp[l][r][k] != 0)
            return dp[l][r][k];
     
        // else calculate the value
        int sum_ = sum(arr, l, r);
        int len_r = (r - l + 1) - k;
        int len = (r - l + 1);
        int ans = 0;
     
        // select all the sub array of length len_r
        for (int i = 0; i < len - len_r + 1; i++)
        {
            // get the sum of that sub array
            int sum_sub = sum(arr, i + l, i + l + len_r - 1);
     
            // check if it is the maximum or not
            ans = Math.max(ans, (sum_ - sum_sub) + (sum_sub -
                    solve(arr, i + l, i + l + len_r - 1, k)));
        }
     
        // store it in the table
        dp[l][r][k] = ans;
     
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
     
        int arr[] = { 10, 15, 20, 9, 2, 5 }, k = 2;
        int n = arr.length;
 
        System.out.println(solve(arr, 0, n - 1, k));
     
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the above approach
import numpy as np
 
# Function to return sum of subarray from l to r
def Sum(arr, l, r) :
 
    # calculate sum by a loop from l to r
    s = 0;
    for i in range(l, r + 1) :
        s += arr[i];
 
    return s;
 
# dp to store the values of sub problems
dp = np.zeros((101, 101, 101));
 
def solve(arr, l, r, k) :
 
    # if length of the array is less than k
    # return the sum
    if (r - l + 1 <= k) :
        return Sum(arr, l, r);
 
    # if the value is previously calculated
    if (dp[l][r][k]) :
        return dp[l][r][k];
 
    # else calculate the value
    sum_ = Sum(arr, l, r);
    len_r = (r - l + 1) - k;
    length = (r - l + 1);
    ans = 0;
 
    # select all the sub array of length len_r
    for i in range(length - len_r + 1) :
         
        # get the sum of that sub array
        sum_sub = Sum(arr, i + l, i + l + len_r - 1);
 
        # check if it is the maximum or not
        ans = max(ans, (sum_ - sum_sub) + (sum_sub -
                            solve(arr, i + l, i + l + len_r - 1, k)));
 
    # store it in the table
    dp[l][r][k] = ans;
 
    return ans;
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 10, 15, 20, 9, 2, 5 ]; k = 2;
     
    n = len(arr);
 
    print(solve(arr, 0, n - 1, k));
 
# This code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
 
class GFG
{
     
    // Function to return sum of subarray from l to r
    static int sum(int []arr, int l, int r)
    {
        // calculate sum by a loop from l to r
        int s = 0;
        for (int i = l; i <= r; i++)
        {
            s += arr[i];
        }
        return s;
    }
     
    // dp to store the values of sub problems
    static int [,,]dp = new int[101, 101, 101] ;
     
    static int solve(int []arr, int l, int r, int k)
    {
        // if length of the array is less than k
        // return the sum
        if (r - l + 1 <= k)
            return sum(arr, l, r);
     
        // if the value is previously calculated
        if (dp[l, r, k] != 0)
            return dp[l, r, k];
     
        // else calculate the value
        int sum_ = sum(arr, l, r);
        int len_r = (r - l + 1) - k;
        int len = (r - l + 1);
        int ans = 0;
     
        // select all the sub array of length len_r
        for (int i = 0; i < len - len_r + 1; i++)
        {
            // get the sum of that sub array
            int sum_sub = sum(arr, i + l, i + l + len_r - 1);
     
            // check if it is the maximum or not
            ans = Math.Max(ans, (sum_ - sum_sub) + (sum_sub -
                    solve(arr, i + l, i + l + len_r - 1, k)));
        }
     
        // store it in the table
        dp[l, r, k] = ans;
     
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 10, 15, 20, 9, 2, 5 };
        int k = 2;
        int n = arr.Length;
 
        Console.WriteLine(solve(arr, 0, n - 1, k));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
    // JavaScript implementation of the above approach
     
    // Function to return sum of subarray from l to r
    function sum(arr, l, r)
    {
        // calculate sum by a loop from l to r
        let s = 0;
        for (let i = l; i <= r; i++)
        {
            s += arr[i];
        }
        return s;
    }
       
    // dp to store the values of sub problems
    let dp = new Array(101);
    for (let i = 0; i < 101; i++)
    {
        dp[i] = new Array(101);
        for (let j = 0; j < 101; j++)
        {
            dp[i][j] = new Array(101);
            for (let k = 0; k < 101; k++)
            {
                dp[i][j][k] = 0;
            }
        }
    }
       
    function solve(arr, l, r, k)
    {
        // if length of the array is less than k
        // return the sum
        if (r - l + 1 <= k)
            return sum(arr, l, r);
       
        // if the value is previously calculated
        if (dp[l][r][k] != 0)
            return dp[l][r][k];
       
        // else calculate the value
        let sum_ = sum(arr, l, r);
        let len_r = (r - l + 1) - k;
        let len = (r - l + 1);
        let ans = 0;
       
        // select all the sub array of length len_r
        for (let i = 0; i < len - len_r + 1; i++)
        {
            // get the sum of that sub array
            let sum_sub = sum(arr, i + l, i + l + len_r - 1);
       
            // check if it is the maximum or not
            ans = Math.max(ans, (sum_ - sum_sub) + (sum_sub -
                    solve(arr, i + l, i + l + len_r - 1, k)));
        }
       
        // store it in the table
        dp[l][r][k] = ans;
       
        return ans;
    }
     
    let arr = [ 10, 15, 20, 9, 2, 5 ], k = 2;
    let n = arr.length;
 
    document.write(solve(arr, 0, n - 1, k));
     
</script>

32

Complejidad temporal: O(r ² )

Espacio auxiliar: O (101 * 101 * 101)