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