Nos han dado N globos, cada uno con una cantidad de monedas asociadas. Al reventar un globo i, el número de monedas ganadas es igual a A[i-1]*A[i]*A[i+1]. Además, los globos i-1 e i+1 ahora se vuelven adyacentes. Encuentre la ganancia máxima posible obtenida después de reventar todos los globos. Suponga un 1 adicional en cada límite.
Ejemplos:
Input : 5, 10
Output : 60
Explanation - First Burst 5, Coins = 1*5*10
Then burst 10, Coins+= 1*10*1
Total = 60
Input : 1, 2, 3, 4, 5
Output : 110
Una solución recursiva se discute aquí . Podemos resolver este problema usando programación dinámica.
Primero, considere una sub-array de índices de izquierda a derecha (inclusive).
Si asumimos que el globo en el índice Last es el último globo en explotar en este subconjunto, diríamos que el acuñado ganado es -A[left-1]*A[last]*A[right+1].
Además, el total de monedas ganadas sería este valor, más dp[izquierda][último – 1] + dp[último + 1][derecha], donde dp[i][j] significa la cantidad máxima de monedas ganadas para la subarray con índices yo, j.
Por lo tanto, para cada valor de Izquierda y Derecha, necesitamos encontrar y elegir un valor de Último con el máximo de monedas ganadas y actualizar la array dp.
Nuestra respuesta es el valor en dp[1][N].
C++
// C++ program burst balloon problem
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int getMax(int A[], int N)
{
// Add Bordering Balloons
int B[N + 2];
B[0] = 1;
B[N + 1] = 1;
for (int i = 1; i <= N; i++)
B[i] = A[i - 1];
// Declare DP Array
int dp[N + 2][N + 2];
memset(dp, 0, sizeof(dp));
for (int length = 1; length < N + 1; length++)
{
for (int left = 1; left < N - length + 2; left++)
{
int right = left + length - 1;
// For a sub-array from indices left, right
// This innermost loop finds the last balloon burst
for (int last = left; last < right + 1; last++)
{
dp[left][right] = max(dp[left][right],
dp[left][last - 1] +
B[left - 1] * B[last] * B[right + 1] +
dp[last + 1][right]);
}
}
}
return dp[1][N];
}
// Driver code
int main()
{
int A[] = { 1, 2, 3, 4, 5 };
// Size of the array
int N = sizeof(A) / sizeof(A[0]);
// Calling function
cout << getMax(A, N) << endl;
}
// This code is contributed by ashutosh450
Java
// Java program to illustrate
// Burst balloon problem
import java.util.Arrays;
class GFG{
public static int getMax(int[] A, int N)
{
// Add Bordering Balloons
int[] B = new int[N + 2];
B[0] = B[N + 1] = 1;
for(int i = 1; i <= N; i++)
B[i] = A[i - 1];
// Declaring DP array
int[][] dp = new int[N + 2][N + 2];
for(int length = 1;
length < N + 1; length++)
{
for(int left = 1;
left < N - length + 2; left++)
{
int right = left + length -1;
// For a sub-array from indices
// left, right. This innermost
// loop finds the last balloon burst
for(int last = left;
last < right + 1; last++)
{
dp[left][right] = Math.max(
dp[left][right],
dp[left][last - 1] +
B[left - 1] * B[last] *
B[right + 1] +
dp[last + 1][right]);
}
}
}
return dp[1][N];
}
// Driver code
public static void main(String args[])
{
int[] A = { 1, 2, 3, 4, 5 };
// Size of the array
int N = A.length;
// Calling function
System.out.println(getMax(A, N));
}
}
// This code is contributed by dadi madhav
Python3
# Python3 program burst balloon problem. def getMax(A): N = len(A) A = [1] + A + [1]# Add Bordering Balloons dp = [[0 for x in range(N + 2)] for y in range(N + 2)]# Declare DP Array for length in range(1, N + 1): for left in range(1, N-length + 2): right = left + length -1 # For a sub-array from indices left, right # This innermost loop finds the last balloon burst for last in range(left, right + 1): dp[left][right] = max(dp[left][right], \ dp[left][last-1] + \ A[left-1]*A[last]*A[right + 1] + \ dp[last + 1][right]) return(dp[1][N]) # Driver code A = [1, 2, 3, 4, 5] print(getMax(A))
C#
// C# program to illustrate
// Burst balloon problem
using System;
class GFG{
public static int getMax(int[] A, int N)
{
// Add Bordering Balloons
int[] B = new int[N + 2];
B[0] = B[N + 1] = 1;
for(int i = 1; i <= N; i++)
B[i] = A[i - 1];
// Declaring DP array
int[,] dp = new int[(N + 2), (N + 2)];
for(int length = 1;
length < N + 1; length++)
{
for(int left = 1;
left < N - length + 2; left++)
{
int right = left + length -1;
// For a sub-array from indices
// left, right. This innermost
// loop finds the last balloon burst
for(int last = left;
last < right + 1; last++)
{
dp[left, right] = Math.Max(
dp[left, right],
dp[left, last - 1] +
B[left - 1] * B[last] *
B[right + 1] +
dp[last + 1, right]);
}
}
}
return dp[1, N];
}
// Driver code
public static void Main()
{
int[] A = new int[] { 1, 2, 3, 4, 5 };
// Size of the array
int N = A.Length;
// Calling function
Console.WriteLine(getMax(A, N));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program burst balloon problem
function getMax(A, N)
{
// Add Bordering Balloons
var B = new Array(N+2);
B[0] = 1;
B[N + 1] = 1;
for (var i = 1; i <= N; i++)
B[i] = A[i - 1];
// Declare DP Array
var dp = new Array(N + 2);
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(N + 2).fill(0);
}
for (var length = 1; length < N + 1; length++)
{
for (var left = 1; left < N - length + 2; left++)
{
var right = left + length - 1;
// For a sub-array from indices left, right
// This innermost loop finds the last balloon burst
for (var last = left; last < right + 1; last++)
{
dp[left][right] = Math.max(dp[left][right],
dp[left][last - 1] +
B[left - 1] * B[last] * B[right + 1] +
dp[last + 1][right]);
}
}
}
return dp[1][N];
}
// Driver code
var A = [ 1, 2, 3, 4, 5 ];
// Size of the array
var N = A.length;
// Calling function
document.write(getMax(A, N));
// This code is contributed by shubhamsingh10
</script>
110
Publicación traducida automáticamente
Artículo escrito por joshi_arihant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA