Dados dos enteros positivos N y K , la tarea es encontrar el número de strings de longitud K que se pueden generar a partir de los primeros N alfabetos de modo que los caracteres de la string se ordenen lexicográficamente.
Ejemplos:
Entrada: N = 5, K = 2
Salida: 15
Explicación: Todas las strings posibles son {“AA”, “AB”, “AC”, “AD”, “AE”, “BB”, “BC”, “BD” , “BE”, “CC”, “CD”, “CE”, “DD”, “DE”, “EE”}.Entrada: N = 7, K = 10
Salida: 8008
Enfoque ingenuo: el enfoque más simple para resolver el problema es usar recursión y retroceso para generar todos los arreglos posibles de caracteres y, para cada string, verificar si los caracteres siguen un orden lexicográfico creciente o no. Imprime el recuento de todas esas strings.
Complejidad temporal: O(K N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica , ya que hay subproblemas superpuestos que se pueden memorizar o tabular en las llamadas recursivas mediante el uso de una array 2D auxiliar dp[][] y calcular el valor de cada estado en el enfoque de abajo hacia arriba.
dp[i][j] representa el número de formas de organizar strings de longitud “i” con las letras distintas “j” .
dp[i][j] = dp[i][j – 1] (Elige no comenzar con la primera letra)
+ dp[i – 1][j – 1] (Elige la primera letra de la string como primera letra)
+ dp[i – 2][j – 1] (Elija las 2 primeras letras de la string como primera letra)
+ ….
+ ….
+ dp[0][j – 1] (Elija las primeras i letras de la string como primera letra)
dp[i][j] = Suma de todos los valores de la (j-1) columna para las filas “i”
Siga los pasos a continuación para resolver este problema:
- Inicialice una array columnSum[] de tamaño (N+1) , donde columnSum[i] es la suma de todos los valores en la columna «j» de la array dp[][] .
- Inicialice una tabla dp[][] de tamaño (K + 1)*(N + 1) .
- Inicialice dp[0][i] como 1 y luego actualice la array columnSum[] .
- Iterar dos bucles anidados sobre K y usando la variable i y j respectivamente:
- Almacene dp[i][j] como columnSum[j – 1] .
- Actualice columnSum[j] como columnSum[j] + dp[i][j] .
- Después de los pasos anteriores, imprima el valor de dp[K][N] como el número resultante de formas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count K-length // strings from first N alphabets void waysToArrangeKLengthStrings( int N, int K) { // To keep track of column sum in dp int column_sum[N + 1] = { 0 }, i, j; // Auxiliary 2d dp array int dp[K + 1][N + 1] = { 0 }; // Initialize dp[0][i] = 1 and // update the column_sum for (i = 0; i <= N; i++) { dp[0][i] = 1; column_sum[i] = 1; } // Iterate for K times for (i = 1; i <= K; i++) { // Iterate for N times for (j = 1; j <= N; j++) { // dp[i][j]: Stores the number // of ways to form i-length // strings consisting of j letters dp[i][j] += column_sum[j - 1]; // Update the column_sum column_sum[j] += dp[i][j]; } } // Print number of ways to arrange // K-length strings with N alphabets cout << dp[K][N]; } // Driver Code int main() { // Given N and K int N = 5, K = 2; // Function Call waysToArrangeKLengthStrings(N, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to count K-length // strings from first N alphabets static void waysToArrangeKLengthStrings( int N, int K) { // To keep track of column sum in dp int[] column_sum = new int[N + 1]; int i, j; for(i = 1; i < N + 1; i++) { column_sum[i] = 0; } // Auxiliary 2d dp array int dp[][] = new int[K + 1][N + 1]; for(i = 1; i < K + 1; i++) { for(j = 1; j < N + 1; j++) { dp[i][j] = 0; } } // Initialize dp[0][i] = 1 and // update the column_sum for(i = 0; i <= N; i++) { dp[0][i] = 1; column_sum[i] = 1; } // Iterate for K times for(i = 1; i <= K; i++) { // Iterate for N times for(j = 1; j <= N; j++) { // dp[i][j]: Stores the number // of ways to form i-length // strings consisting of j letters dp[i][j] += column_sum[j - 1]; // Update the column_sum column_sum[j] += dp[i][j]; } } // Print number of ways to arrange // K-length strings with N alphabets System.out.print(dp[K][N]); } // Driver Code public static void main(String[] args) { // Given N and K int N = 5, K = 2; // Function Call waysToArrangeKLengthStrings(N, K); } } // This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to count K-length # strings from first N alphabets def waysToArrangeKLengthStrings(N, K): # To keep track of column sum in dp column_sum = [0 for i in range(N + 1)] i = 0 j = 0 # Auxiliary 2d dp array dp = [[0 for i in range(N + 1)] for j in range(K + 1)] # Initialize dp[0][i] = 1 and # update the column_sum for i in range(N + 1): dp[0][i] = 1 column_sum[i] = 1 # Iterate for K times for i in range(1, K + 1): # Iterate for N times for j in range(1, N + 1): # dp[i][j]: Stores the number # of ways to form i-length # strings consisting of j letters dp[i][j] += column_sum[j - 1] # Update the column_sum column_sum[j] += dp[i][j] # Print number of ways to arrange # K-length strings with N alphabets print(dp[K][N]) # Driver Code if __name__ == '__main__': # Given N and K N = 5 K = 2 # Function Call waysToArrangeKLengthStrings(N, K) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach using System; class GFG{ // Function to count K-length // strings from first N alphabets static void waysToArrangeKLengthStrings(int N, int K) { // To keep track of column sum in dp int[] column_sum = new int[N + 1]; int i, j; for(i = 1; i < N + 1; i++) { column_sum[i] = 0; } // Auxiliary 2d dp array int[,] dp = new int[K + 1, N + 1]; for(i = 1; i < K + 1; i++) { for(j = 1; j < N + 1; j++) { dp[i, j] = 0; } } // Initialize dp[0][i] = 1 and // update the column_sum for(i = 0; i <= N; i++) { dp[0, i] = 1; column_sum[i] = 1; } // Iterate for K times for(i = 1; i <= K; i++) { // Iterate for N times for(j = 1; j <= N; j++) { // dp[i][j]: Stores the number // of ways to form i-length // strings consisting of j letters dp[i, j] += column_sum[j - 1]; // Update the column_sum column_sum[j] += dp[i, j]; } } // Print number of ways to arrange // K-length strings with N alphabets Console.Write(dp[K, N]); } // Driver Code public static void Main() { // Given N and K int N = 5, K = 2; // Function Call waysToArrangeKLengthStrings(N, K); } } // This code is contributed by code_hunt
Javascript
<script> // Javascript program to implement // the above approach // Function to count K-length // strings from first N alphabets function waysToArrangeKLengthStrings(N, K) { // To keep track of column sum in dp let column_sum = []; let i, j; for(i = 1; i < N + 1; i++) { column_sum[i] = 0; } // Auxiliary 2d dp array let dp = new Array(K + 1); // Loop to create 2D array using 1D array for (i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for(i = 1; i < K + 1; i++) { for(j = 1; j < N + 1; j++) { dp[i][j] = 0; } } // Initialize dp[0][i] = 1 and // update the column_sum for(i = 0; i <= N; i++) { dp[0][i] = 1; column_sum[i] = 1; } // Iterate for K times for(i = 1; i <= K; i++) { // Iterate for N times for(j = 1; j <= N; j++) { // dp[i][j]: Stores the number // of ways to form i-length // strings consisting of j letters dp[i][j] += column_sum[j - 1]; // Update the column_sum column_sum[j] += dp[i][j]; } } // Print number of ways to arrange // K-length strings with N alphabets document.write(dp[K][N]); } // Driver Code // Given N and K let N = 5, K = 2; // Function Call waysToArrangeKLengthStrings(N, K); // This code is contributed by splevel62. </script>
15
Complejidad temporal: O(N*K)
Espacio auxiliar: O(N*K)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA