Dado un número N que representa la longitud de una secuencia de corchetes que consta de corchetes ‘(‘, ‘)’. La secuencia real no se conoce de antemano. Dados los valores de ambos corchetes ‘(‘ y ‘)’ si se colocan en el índice de la expresión.
La tarea es encontrar la suma mínima posible de cualquier secuencia de paréntesis de longitud N utilizando la información anterior.
Aquí adj[i][0] representa el valor asignado al corchete ‘)’ en el i-ésimo índice y adj[i][1] representa el valor asignado al corchete ‘(‘ en el i-ésimo índice.
Restricciones :
- Debe haber N/2 pares hechos de corchetes. Es decir, N/2 pares de ‘(‘, ‘)’.
- Encuentre la suma mínima de la expresión de paréntesis adecuada.
- El índice comienza desde 0.
Ejemplos :
Input : N = 4 adj[N][2] ={{5000, 3000}, {6000, 2000}, {8000, 1000}, {9000, 6000}} Output : 19000 Assigning first index as '(' for proper bracket expression is (_ _ _ . Now all the possible bracket expressions are ()() and (()). where '(' denotes as adj[i][1] and ')' denotes as adj[i][0]. Hence, for ()() sum is 3000+6000+1000+9000=19000. and (()), sum is 3000+2000+8000+9000=220000. Thus answer is 19000 Input : N = 4 adj[N][2] = {{435, 111}, {43, 33}, {1241, 1111}, {234, 22}} Output : 1499
Algoritmo :
- El primer elemento de la secuencia de paréntesis solo puede ser ‘(‘, por lo tanto, el valor de adj[0][1] solo se usa en el índice 0.
- Llame a una función para encontrar una expresión de paréntesis adecuada usando dp como se explica en este artículo .
- Denotar ‘(‘ como adj[i][1] y ‘)’ como adj[i][0].
- Encuentre la suma mínima de todas las posibles expresiones correctas entre paréntesis.
- Devuelve la respuesta + adj[0][1].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Minimum sum possible // of any bracket sequence of length N using // the given values for brackets #include <bits/stdc++.h> using namespace std; #define MAX_VAL 10000000 // DP array int dp[100][100]; // Recursive function to check for // correct bracket expression int find(int index, int openbrk, int n, int adj[][2]) { /// Not a proper bracket expression if (openbrk < 0) return MAX_VAL; // If reaches at end if (index == n) { /// If proper bracket expression if (openbrk == 0) { return 0; } else // if not, return max return MAX_VAL; } // If already visited if (dp[index][openbrk] != -1) return dp[index][openbrk]; // To find out minimum sum dp[index][openbrk] = min(adj[index][1] + find(index + 1, openbrk + 1, n, adj), adj[index][0] + find(index + 1, openbrk - 1, n, adj)); return dp[index][openbrk]; } // Driver Code int main() { int n = 4; int adj[n][2] = { { 5000, 3000 }, { 6000, 2000 }, { 8000, 1000 }, { 9000, 6000 } }; memset(dp, -1, sizeof(dp)); cout << find(1, 1, n, adj) + adj[0][1] << endl; return 0; }
Java
// Java program to find the Minimum sum possible // of any bracket sequence of length N using // the given values for brackets public class GFG { final static int MAX_VAL = 10000000 ; // DP array static int dp[][] = new int[100][100]; // Recursive function to check for // correct bracket expression static int find(int index, int openbrk, int n, int adj[][]) { /// Not a proper bracket expression if (openbrk < 0) return MAX_VAL; // If reaches at end if (index == n) { /// If proper bracket expression if (openbrk == 0) { return 0; } else // if not, return max return MAX_VAL; } // If already visited if (dp[index][openbrk] != -1) return dp[index][openbrk]; // To find out minimum sum dp[index][openbrk] = Math.min(adj[index][1] + find(index + 1, openbrk + 1, n, adj), adj[index][0] + find(index + 1, openbrk - 1, n, adj)); return dp[index][openbrk]; } // Driver code public static void main(String args[]) { int n = 4; int adj[][] = { { 5000, 3000 }, { 6000, 2000 }, { 8000, 1000 }, { 9000, 6000 } }; for (int i = 0; i < dp.length; i ++) for (int j = 0; j < dp.length; j++) dp[i][j] = -1 ; System.out.println(find(1, 1, n, adj) + adj[0][1]); } // This code is contributed by ANKITRAI1 }
Python3
# Python 3 program to find the Minimum sum # possible of any bracket sequence of length # N using the given values for brackets MAX_VAL = 10000000 # DP array dp = [[-1 for i in range(100)] for i in range(100)] # Recursive function to check for # correct bracket expression def find(index, openbrk, n, adj): # Not a proper bracket expression if (openbrk < 0): return MAX_VAL # If reaches at end if (index == n): # If proper bracket expression if (openbrk == 0): return 0 # if not, return max else: return MAX_VAL # If already visited if (dp[index][openbrk] != -1): return dp[index][openbrk] # To find out minimum sum dp[index][openbrk] = min(adj[index][1] + find(index + 1, openbrk + 1, n, adj), adj[index][0] + find(index + 1, openbrk - 1, n, adj)) return dp[index][openbrk] # Driver Code if __name__ == '__main__': n = 4; adj = [[5000, 3000],[6000, 2000], [8000, 1000],[9000, 6000]] print(find(1, 1, n, adj) + adj[0][1]) # This code is contributed by # Sanjit_Prasad
C#
// C# program to find the Minimum sum possible // of any bracket sequence of length N using // the given values for brackets using System; class GFG { public static int MAX_VAL = 10000000; // DP array public static int[,] dp = new int[100,100]; // Recursive function to check for // correct bracket expression public static int find(int index, int openbrk, int n, int[,] adj) { /// Not a proper bracket expression if (openbrk < 0) return MAX_VAL; // If reaches at end if (index == n) { /// If proper bracket expression if (openbrk == 0) { return 0; } else // if not, return max return MAX_VAL; } // If already visited if (dp[index,openbrk] != -1) return dp[index,openbrk]; // To find out minimum sum dp[index,openbrk] = Math.Min(adj[index,1] + find(index + 1, openbrk + 1, n, adj), adj[index,0] + find(index + 1, openbrk - 1, n, adj)); return dp[index,openbrk]; } // Driver Code static void Main() { int n = 4; int[,] adj = new int[,]{ { 5000, 3000 }, { 6000, 2000 }, { 8000, 1000 }, { 9000, 6000 } }; for(int i = 0; i < 100; i++) for(int j = 0; j < 100; j++) dp[i,j] = -1; Console.Write(find(1, 1, n, adj) + adj[0,1] + "\n"); } //This code is contributed by DrRoot_ }
PHP
<?php // PHP program to find the Minimum sum possible // of any bracket sequence of length N using // the given values for brackets $MAX_VAL = 10000000; $dp = array_fill(0, 100, array_fill(0, 100, -1)); // Recursive function to check for // correct bracket expression function find($index, $openbrk, $n, $adj) { global $MAX_VAL; global $dp; /// Not a proper bracket expression if ($openbrk < 0) return $MAX_VAL; // If reaches at end if ($index == $n) { /// If proper bracket expression if ($openbrk == 0) { return 0; } else // if not, return max return $MAX_VAL; } // If already visited if ($dp[$index][$openbrk] != -1) return $dp[$index][$openbrk]; // To find out minimum sum $dp[$index][$openbrk] = min($adj[$index][1] + find($index + 1, $openbrk + 1, $n, $adj), $adj[$index][0] + find($index + 1, $openbrk - 1, $n, $adj)); return $dp[$index][$openbrk]; } // Driver Code $n = 4; $adj = array(array(5000, 3000), array(6000, 2000), array(8000, 1000), array(9000, 6000)); echo find(1, 1, $n, $adj) + $adj[0][1]; // This code is contributed by ihritik ?>
Javascript
<script> // Javascript program to find the Minimum sum possible // of any bracket sequence of length N using // the given values for brackets let MAX_VAL = 10000000 ; // DP array let dp = new Array(100); for(let i = 0; i < 100; i++) { dp[i] = new Array(100); for(let j = 0; j < 100; j++) { dp[i][j] = 0; } } // Recursive function to check for // correct bracket expression function find(index, openbrk, n, adj) { /// Not a proper bracket expression if (openbrk < 0) return MAX_VAL; // If reaches at end if (index == n) { /// If proper bracket expression if (openbrk == 0) { return 0; } else // if not, return max return MAX_VAL; } // If already visited if (dp[index][openbrk] != -1) return dp[index][openbrk]; // To find out minimum sum dp[index][openbrk] = Math.min(adj[index][1] + find(index + 1, openbrk + 1, n, adj), adj[index][0] + find(index + 1, openbrk - 1, n, adj)); return dp[index][openbrk]; } let n = 4; let adj = [ [ 5000, 3000 ], [ 6000, 2000 ], [ 8000, 1000 ], [ 9000, 6000 ] ]; for (let i = 0; i < dp.length; i ++) for (let j = 0; j < dp.length; j++) dp[i][j] = -1 ; document.write(find(1, 1, n, adj) + adj[0][1]); // This code is contributed by divyesh072019. </script>
Producción:
19000
Tiempo Complejidad : O(N 2 )