Costo mínimo para construir N bloques a partir de un bloque

Dado un número N, la tarea es construir N bloques a partir de 1 bloque realizando la siguiente operación:

1. Duplica el número de bloques presentes en el contenedor y el costo de esta operación es X.
2. Aumente el número de bloques presentes en el contenedor en uno y el costo de esta operación es Y.
3. Disminuya en uno el número de bloques presentes en el contenedor y el costo de esta operación es Z.

Ejemplos:

Entrada: N = 5, X = 2, Y = 1, Z = 3
Salida: 4
Explicación:
En la primera operación, simplemente aumente el número de bloques en uno, costo = 1 y número de bloques = 2
En la segunda operación, duplique los bloques , costo = 3 y número de bloques = 4
En la tercera operación, aumente nuevamente el número_de_bloques en uno, costo = 4 y número de bloques = 5
Entonces costo mínimo = 4

Entrada: N = 7, X = 1, Y = 7, Z = 2
Salida: 5

Acercarse:

• Let f(i)denota el costo mínimo para construir ibloques. So f(i)=min(f(2*i)+X, f(i-1)+Y, f(i+1)+Z)
  Aquí el valor actual depende de su próximo valor así como de su valor anterior, pero sabe que en la programación dinámica el valor actual depende solo de su valor anterior. Así que intente convertir su próximo valor a su valor anterior. Podemos escribir f(2*i)como f(i/2)porque cuando ya hemos construido i/2 bloques, entonces podemos duplicar el número de bloques actuales o aumentar el número de bloques en 1 o disminuir el número de bloques en 1. Aquí no es necesario calcular f(2*i).
  Ahora

  f(i) = min(f(i/2)+X, f(i-1)+Y, f(i+1)+Z)

• Si ies par entonces (i+1)debe ser impar. Podemos construir (i)bloques solo realizando la operación de incremento y la operación doble, por lo que no es necesario realizar la operación de decremento, ¿por qué?
  Esto se debe a que (i+1)es un número impar. Entonces, si construye (i+1)bloques realizando una operación de incremento, se confirma que ya hemos construido ibloques, lo que significa que tenemos el costo mínimo de construir ibloques. Si realizamos cualquier otra operación, debe aumentar su costo óptimo que es irrelevante. Entonces relación de recurrencia cuando i es par:

  f(i)=min(f(i/2)+X, f(i-1)+Y)

• Si ies impar entonces (i+1)debe ser par. Podemos construir (i+1)bloques solo realizando una operación doble o una operación decreciente, ¿por qué no una operación de incremento?
  Esto se debe a que si ya ha construido ibloques, entonces no es necesario construir (i+1)bloques porque agregará más costos. Entonces podemos calcular f(i+1)=f((i+1)/2)+ X.la relación de recurrencia cuando i es impar:

  f(i)=min(f(i-1)+Y, f( (i+1)/2)+X+Z)

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

CPP

// C++ program to Minimum cost // to build N blocks from one block    #include <bits/stdc++.h> using namespace std;    // Function to calculate // min cost to build N blocks int minCost(int n, int x, int y, int z) {     int dp[n + 1] = { 0 };        // Initialize base case     dp[0] = dp[1] = 0;        for (int i = 2; i <= n; i++) {         // Recurence when         // i is odd         if (i % 2 == 1) {             dp[i] = min(                 dp[(i + 1) / 2] + x + z,                 dp[i - 1] + y);         }         // Recurence when         // i is even         else {             dp[i] = min(dp[i / 2] + x,                         dp[i - 1] + y);         }     }        return dp[n]; }    // Driver code int main() {     int n = 5, x = 2, y = 1, z = 3;     cout << minCost(n, x, y, z) << endl;        return 0; }

Java

// Java program to Minimum cost // to build N blocks from one block class GFG {    // Function to calculate // min cost to build N blocks static int minCost(int n, int x, int y, int z) {     int dp[] = new int[n + 1];        // Initialize base case     dp[0] = dp[1] = 0;        for (int i = 2; i <= n; i++)     {         // Recurence when         // i is odd         if (i % 2 == 1)         {             dp[i] = Math.min(                 dp[(i + 1) / 2] + x + z,                 dp[i - 1] + y);         }         // Recurence when         // i is even         else          {             dp[i] = Math.min(dp[i / 2] + x,                         dp[i - 1] + y);         }     }        return dp[n]; }    // Driver code public static void main(String[] args) {     int n = 5, x = 2, y = 1, z = 3;     System.out.print(minCost(n, x, y, z) +"\n");    } }    // This code is contributed by Rajput-Ji

Python

# python3 program to Minimum cost # to build N blocks from one block    # Function to calculate # min cost to build N blocks def minCost(n, x, y, z):     dp = [0] * (n + 1)        # Initialize base case     dp[0] = dp[1] = 0        for i in range(2, n + 1):                    # Recurence when         # i is odd         if (i % 2 == 1):             dp[i] = min(dp[(i + 1) // 2] + x + z, dp[i - 1] + y)                    # Recurence when         # i is even         else:             dp[i] = min(dp[i // 2] + x, dp[i - 1] + y)        return dp[n]    # Driver code n = 5 x = 2 y = 1 z = 3 print(minCost(n, x, y, z))    # This code is contributed by mohit kumar 29

C#

// C# program to Minimum cost // to build N blocks from one block using System;    class GFG {    // Function to calculate // min cost to build N blocks static int minCost(int n, int x, int y, int z) {     int []dp = new int[n + 1];        // Initialize base case     dp[0] = dp[1] = 0;        for (int i = 2; i <= n; i++)     {         // Recurence when         // i is odd         if (i % 2 == 1)         {             dp[i] = Math.Min(                 dp[(i + 1) / 2] + x + z,                 dp[i - 1] + y);         }                    // Recurence when         // i is even         else         {             dp[i] = Math.Min(dp[i / 2] + x,                         dp[i - 1] + y);         }     }     return dp[n]; }    // Driver code public static void Main(String[] args) {     int n = 5, x = 2, y = 1, z = 3;     Console.Write(minCost(n, x, y, z) +"\n"); } }    // This code is contributed by PrinciRaj1992

Producción:

4