Dados dos garrafones con capacidad máxima de m y n litros respectivamente. Las jarras no tienen marcas que puedan ayudarnos a medir cantidades más pequeñas. La tarea es medir d litros de agua usando estos dos cántaros. Por lo tanto, nuestro objetivo es llegar desde el estado inicial (m, n) al estado final (0, d) … Continue reading «Problema con la jarra de agua al usar Memoization»
Dados dos números N y K. Encuentra el número de formas de representar N como la suma de K números de Fibonacci. Ejemplos : Input : n = 12, k = 1 Output : 0 Input : n = 13, k = 3 Output : 2 Explanation : 2 + 3 + 8, 3 + 5 … Continue reading «Número de formas de representar un número como suma de k números de fibonacci»
A continuación se proporciona un algoritmo para encontrar la longitud de la secuencia de números creciente monótonamente más larga en una array A[0 :n-1]. Sea Li la longitud de la secuencia creciente monótonamente más larga que comienza en el índice i en la array. ¿Cuál de las siguientes afirmaciones es verdadera? (A) El algoritmo usa … Continue reading «Algoritmos | Programación Dinámica | Pregunta 3»
¿Cuál de los siguientes algoritmos estándar no está basado en la programación dinámica? (A) Algoritmo de Bellman-Ford para el camino más corto de fuente única (B) Algoritmo de Floyd Warshall para todos los pares de caminos más cortos (C) 0-1 Problema de la mochila (D) Árbol de expansión mínimo de Prim Respuesta: (D) Explicación: El … Continue reading «Algoritmos | Programación Dinámica | Pregunta 7 – Part 1»
Dada una array binaria N x N. El problema es encontrar la subarray de área máxima que tenga una cuenta de 1 más que una cuenta de 0. Ejemplos: Input : mat[][] = { {1, 0, 0, 1}, {0, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 1} } Output : 9 The … Continue reading «Área máxima de subarray que tiene un recuento de 1 uno más que un recuento de 0»
Dado un entero N y una array 2D cost[][3] , donde cost[i][0] , cost[i][1] y cost[i][2] es el costo de pintar i -ésima casa con colores rojo , azul y verde respectivamente, la tarea es encontrar el costo mínimo para pintar todas las casas de modo que no haya dos casas adyacentes del mismo color. … Continue reading «Minimice el costo de pintar N casas de modo que las casas adyacentes tengan diferentes colores»
Dado N, encuentre el número total de BST únicos que se pueden hacer usando valores de 1 a N. Ejemplos: Input: n = 3 Output: 5 For n = 3, preorder traversal of Unique BSTs are: 1. 1 2 3 2. 1 3 2 3. 2 1 3 4. 3 1 2 5. 3 2 … Continue reading «Número de BST únicos con una clave determinada | Programación dinámica»
Dada una array arr[] de N enteros positivos. La tarea es encontrar la longitud de la subsecuencia más corta tal que el GCD de la subsecuencia sea 1. Si ninguna de las subsecuencias tiene GCD 1, imprima «-1 «. Ejemplos: Entrada: arr[] = {2, 6, 12, 3} Salida: 2 Explicación: El GCD de 2, … Continue reading «Longitud mínima de subsecuencia que tiene unidad GCD»
El problema de suma de subconjuntos se define de la siguiente manera. Dado un conjunto de n enteros positivos, S = {a1 ,a2 ,a3 ,…,an} y el entero positivo W, ¿existe un subconjunto de S cuyos elementos suman W? Un programa dinámico para resolver este problema utiliza una array booleana bidimensional X, con n filas … Continue reading «Algoritmos | Programación Dinámica | Pregunta 7 – Part 2»
Dada una array arr[] y un entero K , la tarea es encontrar el producto mínimo de una subsecuencia donde los elementos adyacentes de la subsecuencia están separados por una distancia máxima de K. Nota: la subsecuencia debe incluir el primer y el último elemento de la array Ejemplos: Entrada: arr[] = { 1, 2, … Continue reading «Subsecuencia mínima de productos donde los elementos adyacentes están separados por una distancia máxima de K»