Puntuación mínima posible para un jugador seleccionando uno o dos elementos de array consecutivos de una array binaria dada

Dada una array binaria arr[] de tamaño N y dos jugadores , A y B. La tarea es minimizar la puntuación del jugador A seleccionando las puntuaciones de los jugadores según las restricciones dadas:

• Cada jugador puede eliminar uno o dos números consecutivos en su turno de la array y los elementos se eliminan en el orden de izquierda a derecha.
• Los jugadores tendrán turnos alternos, empezando por el jugador A.
• Inicialmente, la penalización es 0 y se incrementa en números, que el jugador A elimina.

Ejemplos:

Entrada: arr[] = {1, 1, 1, 1, 0, 0, 1}
Salida: 2
Explicación: los elementos se pueden eliminar de la siguiente manera:
Turno 1: el jugador A elimina el elemento en el índice 0. Por lo tanto, la penalización es 0 + 1 = 1.
Turno 2: el jugador B elimina los elementos en los índices 1 y 2. Aún así, la penalización es 1.
Turno 3: el jugador A elimina el elemento en el índice 3. Por lo tanto, la penalización es 1 + 1 = 2.
Turno 4: El jugador B elimina el elemento del índice 4. Aún así, la penalización es 2.
Turno 5: El jugador A elimina el elemento del índice 5. Aún así, la penalización es 2 + 0 = 2.
Turno 6: El jugador B elimina el elemento del índice 6. Aún , la penalización es 2.
Por lo tanto, la puntuación mínima para el jugador A = 2.

Entrada: arr[] = {1, 0, 1, 1, 0, 1, 1, 1}
Salida: 2
Explicación: los elementos se pueden eliminar de la siguiente manera:
Turno 1: el jugador A elimina el elemento en los índices 0 y 1. Por lo tanto , la penalización es 0 + 1 + 0 = 1.
Turno 2: el jugador B elimina los elementos en los índices 2 y 3. Aún así, la penalización es 1.
Turno 3: el jugador A elimina el elemento en el índice 4. Por lo tanto, la penalización es 1 + 0 = 1.
Turno 4: el jugador B elimina los elementos en los índices 5 y 6. Aún así, la penalización es 1.
Turno 5: el jugador A elimina el elemento en el índice 7. Por lo tanto, la penalización es 2 + 1 = 2.
Por lo tanto, la puntuación mínima para el jugador A = 2.

Enfoque ingenuo: el enfoque más simple es probar todas las combinaciones posibles para eliminar elementos de la array dada. Cada vez, hay dos opciones posibles, es decir, se pueden eliminar uno o dos elementos consecutivos. En cada posición, de 1 a N – 1 , hay 2 opciones. Por lo tanto, se pueden hacer 2 ^N combinaciones posibles. Se pueden encontrar penalizaciones para cada combinación y entre ellas, imprimir la penalización mínima. 

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica . Se puede resolver usando las siguientes transiciones dp , donde dp[i][0] almacena la penalización mínima de i a N – 1 . Si el jugador A comienza a elegir del índice i . De manera similar, dp[i][1] se puede definir para el jugador B.

En el turno del jugador A:
dp[i][0] = min(dp(i+1, 1)+arr[i], dp(i+2, 1)+arr[i+1]+arr[i+2 ])
donde, 
i denota la posición actual.
1 denota que es el turno de B en el siguiente estado.

En el turno del jugador B:
dp[i][1] = min(dp(i+1, 0), dp(i+2, 0))
donde 
i denota la posición actual.
0 denota que es el turno de A en el siguiente estado.

Siga los pasos a continuación para resolver el problema:

• Se puede utilizar la recursividad con memorización . Para la condición base, verifique si la posición actual excede o se convierte en N , devuelva 0
• Aplicar las transiciones definidas anteriormente según el turno del jugador y devolver la respuesta mínima.
• Inicialice la función recursiva con el turno y la penalización del jugador A como 0 .
• Para cada llamada recursiva, almacene el mínimo de penalizaciones calculado en un Mapa M para evitar el cálculo de subproblemas superpuestos .
• Imprima la puntuación mínima para el jugador A después de que finalice la llamada recursiva anterior

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the minimum score for each
// states as map<pair<pos, myturn>, ans>
map<pair<int, int>, int> m;
 
// Function to find the minimum score
// after choosing element from array
int findMinimum(int a[], int n, int pos,
                int myturn)
{
    // Return the stored state
    if (m.find({ pos, myturn }) != m.end()) {
        return m[{ pos, myturn }];
    }
 
    // Base Case
    if (pos >= n) {
        return 0;
    }
 
    // Player A's turn
    if (!myturn) {
 
        // Find the minimum score
        int ans = min(
            findMinimum(a, n, pos + 1, !myturn)
                + a[pos],
            findMinimum(a, n, pos + 2, !myturn)
                + a[pos] + a[pos + 1]);
 
        // Store the current state
        m[{ pos, myturn }] = ans;
 
        // Return the result
        return ans;
    }
 
    // Player B's turn
    if (myturn) {
 
        // Find minimum score
        int ans = min(
            findMinimum(a, n, pos + 1, !myturn),
            findMinimum(a, n, pos + 2, !myturn));
 
        // Store the current state
        m[{ pos, myturn }] = ans;
 
        // Return the result
        return ans;
    }
    return 0;
}
 
// Function that finds the minimum
// penality after choosing element
// from the given binary array
int countPenality(int arr[], int N)
{
    // Starting position of choosing
    // element from array
    int pos = 0;
 
    // 0 denotes player A turn
    // 1 denotes player B turn
    int turn = 0;
 
    // Function Call
    return findMinimum(arr, N, pos, turn);
}
 
// Print the answer for player A and B
void printAnswer(int* arr, int N)
{
 
    // Minimum penalty
    int a = countPenality(arr, N);
 
    // Calculate sum of all arr elements
    int sum = 0;
    for (int i = 0; i < N; i++) {
        sum += arr[i];
    }
 
    // Print the minimum score
    cout << a;
}
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 0, 1, 1, 0, 1, 1, 1 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    printAnswer(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
static class R
{
    int x, y;
     
    public R(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
// Stores the minimum score for each
// states as map<pair<pos, myturn>, ans>
static HashMap<R, Integer> m = new HashMap<>();
 
// Function to find the minimum score
// after choosing element from array
public static int findMinimum(int[] arr, int N,
                              int pos, int turn)
{
     
    // Return the stored state
    R x = new R(pos, turn);
     
    if (m.containsKey(x))
    {
        return m.get(x);
    }
 
    // Base Case
    if (pos >= N - 1)
    {
        return 0;
    }
 
    // Player A's turn
    if (turn == 0)
    {
         
        // Find the minimum score
        int ans = Math.min(
            findMinimum(arr, N, pos + 1, 1) + arr[pos],
            findMinimum(arr, N, pos + 2, 1) + arr[pos] +
                            arr[pos + 1]);
 
        // Store the current state
        R v = new R(pos, turn);
        m.put(v, ans);
 
        // Return the result
        return ans;
    }
 
    // Player B's turn
    if (turn != 0)
    {
         
        // Find minimum score
        int ans = Math.min(
            findMinimum(arr, N, pos + 1, 0),
            findMinimum(arr, N, pos + 2, 0));
 
        // Store the current state
        R v = new R(pos, turn);
        m.put(v, ans);
 
        // Return the result
        return ans;
    }
    return 0;
}
 
// Function that finds the minimum
// penality after choosing element
// from the given binary array
public static int countPenality(int[] arr, int N)
{
     
    // Starting position of choosing
    // element from array
    int pos = 0;
 
    // 0 denotes player A turn
    // 1 denotes player B turn
    int turn = 0;
 
    // Function Call
    return findMinimum(arr, N, pos, turn) + 1;
}
 
// Function to print the answer
public static void printAnswer(int[] arr, int N)
{
     
    // Minimum penalty
    int a = countPenality(arr, N);
     
    // Calculate sum of all arr elements
    int sum = 0;
    for(int i = 0; i < N; i++)
    {
        sum += arr[i];
    }
     
    // Print the minimum score
    System.out.println(a);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 0, 1, 1, 0, 1, 1, 1 };
    int N = 8;
 
    // Function Call
    printAnswer(arr, N);
}
}
 
// This code is contributed by RohitOberoi

# Python3 program for the above approach
  
# Stores the minimum score for each
# states as map<pair<pos, myturn>, ans>
m = dict()
  
# Function to find the minimum score
# after choosing element from array
def findMinimum(a, n, pos, myturn):
 
    # Return the stored state
    if (pos, myturn) in m:
        return m[( pos, myturn )];
     
    # Base Case
    if (pos >= n - 1):
        return 0;
      
    # Player A's turn
    if (not myturn):
  
        # Find the minimum score
        ans = min( findMinimum(a, n, pos + 1, not myturn) + a[pos],
                     findMinimum(a, n, pos + 2, not myturn) + a[pos] + a[pos + 1]);
  
        # Store the current state
        m[( pos, myturn )] = ans;
  
        # Return the result
        return ans;
  
    # Player B's turn
    if (myturn):
  
        # Find minimum score
        ans = min( findMinimum(a, n, pos + 1, not myturn),
                    findMinimum(a, n, pos + 2, not myturn));
  
        # Store the current state
        m[( pos, myturn )] = ans;
  
        # Return the result
        return ans;
     
    return 0;
   
# Function that finds the minimum
# penality after choosing element
# from the given binary array
def countPenality(arr, N):
 
    # Starting position of choosing
    # element from array
    pos = 0;
  
    # 0 denotes player A turn
    # 1 denotes player B turn
    turn = False;
  
    # Function Call
    return findMinimum(arr, N, pos, turn) + 1;
 
# Print the answer for player A and B
def printAnswer(arr, N):
  
    # Minimum penalty
    a = countPenality(arr, N);
  
    # Calculate sum of all arr elements
    sum = 0;
     
    for i in range(N):
     
        sum += arr[i];
      
    # Print the minimum score
    print(a)
     
# Driver Code
if __name__=='__main__':
 
    # Given array arr[]
    arr = [ 1, 0, 1, 1, 0, 1, 1, 1 ]
  
    N = len(arr)
  
    # Function Call
    printAnswer(arr, N);
 
# This code is contributed by rutvik_56

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Stores the minimum score for each
    // states as map<pair<pos, myturn>, ans>
    static Dictionary<Tuple<int,int>, int> m = new Dictionary<Tuple<int,int>, int>();
      
    // Function to find the minimum score
    // after choosing element from array
    static int findMinimum(int[] arr, int N, int pos, int turn)
    {
          
        // Return the stored state
        Tuple<int,int> x = new Tuple<int,int>(pos, turn);
          
        if (m.ContainsKey(x))
        {
            return m[x];
        }
      
        // Base Case
        if (pos >= N - 1)
        {
            return 0;
        }
      
        // Player A's turn
        if (turn == 0)
        {
              
            // Find the minimum score
            int ans = Math.Min(
                findMinimum(arr, N, pos + 1, 1) + arr[pos],
                findMinimum(arr, N, pos + 2, 1) + arr[pos] +
                                arr[pos + 1]);
      
            // Store the current state
            Tuple<int,int> v = new Tuple<int,int>(pos, turn);
            m[v] = ans;
      
            // Return the result
            return ans;
        }
      
        // Player B's turn
        if (turn != 0)
        {
              
            // Find minimum score
            int ans = Math.Min(
                findMinimum(arr, N, pos + 1, 0),
                findMinimum(arr, N, pos + 2, 0));
      
            // Store the current state
            Tuple<int,int> v = new Tuple<int,int>(pos, turn);
            m[v] = ans;
      
            // Return the result
            return ans;
        }
        return 0;
    }
      
    // Function that finds the minimum
    // penality after choosing element
    // from the given binary array
    static int countPenality(int[] arr, int N)
    {
          
        // Starting position of choosing
        // element from array
        int pos = 0;
      
        // 0 denotes player A turn
        // 1 denotes player B turn
        int turn = 0;
      
        // Function Call
        return findMinimum(arr, N, pos, turn) + 1;
    }
      
    // Function to print the answer
    static void printAnswer(int[] arr, int N)
    {
          
        // Minimum penalty
        int a = countPenality(arr, N);
          
        // Calculate sum of all arr elements
        int sum = 0;
        for(int i = 0; i < N; i++)
        {
            sum += arr[i];
        }
          
        // Print the minimum score
        Console.WriteLine(a);
    }
 
  static void Main() {
    int[] arr = { 1, 0, 1, 1, 0, 1, 1, 1 };
    int N = 8;
  
    // Function Call
    printAnswer(arr, N);
  }
}
 
// This code is contributed by decode2207.

<script>
    // Javascript program for the above approach
     
    // Stores the minimum score for each
    // states as map<pair<pos, myturn>, ans>
    let m = new Map();
       
    // Function to find the minimum score
    // after choosing element from array
    function findMinimum(arr, N, pos, turn)
    {
           
        // Return the stored state
        let x = [pos, turn];
           
        if (m.has(x))
        {
            return m[x];
        }
       
        // Base Case
        if (pos >= N - 1)
        {
            return 0;
        }
       
        // Player A's turn
        if (turn == 0)
        {
               
            // Find the minimum score
            let ans = Math.min(
                findMinimum(arr, N, pos + 1, 1) + arr[pos],
                findMinimum(arr, N, pos + 2, 1) + arr[pos] +
                                arr[pos + 1]);
       
            // Store the current state
            let v = [pos, turn];
            m[v] = ans;
       
            // Return the result
            return ans;
        }
       
        // Player B's turn
        if (turn != 0)
        {
               
            // Find minimum score
            let ans = Math.min(
                findMinimum(arr, N, pos + 1, 0),
                findMinimum(arr, N, pos + 2, 0));
       
            // Store the current state
            let v = [pos, turn];
            m[v] = ans;
       
            // Return the result
            return ans;
        }
        return 0;
    }
       
    // Function that finds the minimum
    // penality after choosing element
    // from the given binary array
    function countPenality(arr, N)
    {
           
        // Starting position of choosing
        // element from array
        let pos = 0;
       
        // 0 denotes player A turn
        // 1 denotes player B turn
        let turn = 0;
       
        // Function Call
        return findMinimum(arr, N, pos, turn) + 1;
    }
       
    // Function to print the answer
    function printAnswer(arr, N)
    {
           
        // Minimum penalty
        let a = countPenality(arr, N);
           
        // Calculate sum of all arr elements
        let sum = 0;
        for(let i = 0; i < N; i++)
        {
            sum += arr[i];
        }
           
        // Print the minimum score
        document.write(a);
    }
     
    let arr = [ 1, 0, 1, 1, 0, 1, 1, 1 ];
    let N = 8;
   
    // Function Call
    printAnswer(arr, N);
  
 // This code is contributed by suresh07
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)