Dados tres números enteros N, L y R , la tarea es imprimir el recuento total de formas de formar un collar de N perl como máximo, de modo que los valores de una perla se encuentren en el rango [L, R] y estén en orden ascendente . .
Ejemplos:
Entrada: N = 3, L = 6, R = 9
Salida: 34
Explicación:
El collar se puede formar de las siguientes maneras:
- Los collares de largo uno que se pueden formar son { “6”, “7”, “8”, “9” }.
- Los collares de largo dos, que se pueden formar son { “66”, “67”, “68”, “69”, “77”, “78”, “79”, “88”, “89”, “99 ”}.
- Los collares de longitud tres, que se pueden formar son { “666”, “667”, “668”, “669”, “677”, “678”, “679”, “688”, “689”, “699 ”, “777”, “778”, “779”, “788”, “789”, “799”, “888”, “889”, “899”, “999” }.
Así, en total, el collar se puede formar de (4+10+20 = 34) formas.
Entrada: N = 1, L = 8, R = 9
Salida: 2
Explicación:
El collar se puede formar de las siguientes formas: {“8”, “9”}.
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- El problema se puede resolver usando programación dinámica de 2 estados con suma de prefijo.
- Supongamos que Dp(i, j) almacena la cuenta de formas de formar un collar de tamaño i con valores de perl en el rango [L, j].
- Entonces, el estado de transición en la i -ésima posición se puede definir como:
- Para cada valor j en el rango [L, R],
- Dp(i, j) = Dp(i – 1, L) + Dp(i – 1, L + 1), …, Dp(i – 1, j – 1)+ Dp(i – 1, j)
- Para cada valor j en el rango [L, R],
- La transición anterior se puede optimizar usando la suma de prefijos para cada i como:
- Dp(i, j) = Dp(i, L) + Dp(i, L + 1) +…+ Dp(i, j – 1) + Dp(i, j)
- Por lo tanto, ahora las transiciones se pueden definir como:
- Dp(i, j) = Dp(i-1, j) + Dp(i, j-1)
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 , para almacenar el resultado.
- Inicialice una array 2D , digamos Dp[][] de dimensión N * (R – L + 1) como 0 para almacenar todos los estados DP.
- Iterar sobre el rango [0, N – 1] usando la variable i, y asignar Dp[i][0] = 1.
- Itere sobre el rango [1, R – L] usando la variable i, y actualice Dp[0][i] como Dp[0][i]= Dp[0][i – 1]+1.
- Asigne Dp[0][R – L] a ans.
- Itere sobre el rango [1, N – 1] usando la variable i, y realice las siguientes operaciones:
- Iterar sobre el rango [1, R – L] usando la variable j, y actualizar Dp[i][j] como Dp[i][j] = Dp[i][j – 1] + Dp[i – 1 ][j].
- Incremente el ans por Dp[i][R – L].
- Finalmente, después de completar los pasos anteriores, imprima el ans .
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 total number of ways
int Count(int N, int L, int R)
{
// Stores all DP-states
vector<vector<int> > dp(N,
vector<int>(R - L + 1, 0));
// Stores the result
int ans = 0;
// Traverse the range [0, N]
for (int i = 0; i < N; i++) {
dp[i][0] = 1;
}
// Traverse the range [1, R - L]
for (int i = 1; i < dp[0].size(); i++) {
// Update dp[i][j]
dp[0][i] = dp[0][i - 1] + 1;
}
// Assign dp[0][R-L] to ans
ans = dp[0][R - L];
// Traverse the range [1, N]
for (int i = 1; i < N; i++) {
// Traverse the range [1, R - L]
for (int j = 1; j < dp[0].size(); j++) {
// Update dp[i][j]
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
// Increment ans by dp[i-1][j]
ans += dp[i][R - L];
}
// Return ans
return ans;
}
// Driver Code
int main()
{
// Input
int N = 3;
int L = 6;
int R = 9;
// Function call
cout << Count(N, L, R);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count total number of ways
static int Count(int N, int L, int R)
{
// Stores all DP-states
int[][] dp = new int[N][R - L + 1];
// Stores the result
int ans = 0;
// Traverse the range [0, N]
for(int i = 0; i < N; i++)
{
dp[i][0] = 1;
}
// Traverse the range [1, R - L]
for(int i = 1; i < dp[0].length; i++)
{
// Update dp[i][j]
dp[0][i] = dp[0][i - 1] + 1;
}
// Assign dp[0][R-L] to ans
ans = dp[0][R - L];
// Traverse the range [1, N]
for(int i = 1; i < N; i++)
{
// Traverse the range [1, R - L]
for(int j = 1; j < dp[0].length; j++)
{
// Update dp[i][j]
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
// Increment ans by dp[i-1][j]
ans += dp[i][R - L];
}
// Return ans
return ans;
}
// Driver Code
public static void main(String args[])
{
// Input
int N = 3;
int L = 6;
int R = 9;
// Function call
System.out.println(Count(N, L, R));
}
}
// This code is contributed by avijitmondal1998
Python3
# Python3 program for the above approach # Function to count total number of ways def Count(N, L, R): # Stores all DP-states dp = [[0 for i in range(R - L + 1)] for i in range(N)] # Stores the result ans = 0 # Traverse the range [0, N] for i in range(N): dp[i][0] = 1 # Traverse the range [1, R - L] for i in range(1, len(dp[0])): # Update dp[i][j] dp[0][i] = dp[0][i - 1] + 1 # Assign dp[0][R-L] to ans ans = dp[0][R - L] # Traverse the range [1, N] for i in range(1, N): # Traverse the range [1, R - L] for j in range(1, len(dp[0])): # Update dp[i][j] dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # Increment ans by dp[i-1][j] ans += dp[i][R - L] # Return ans return ans # Driver Code if __name__ == '__main__': # Input N = 3 L = 6 R = 9 # Function call print(Count(N, L, R)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to count total number of ways
static int Count(int N, int L, int R)
{
// Stores all DP-states
int[,] dp = new int[N, R - L + 1];
// Stores the result
int ans = 0;
// Traverse the range [0, N]
for(int i = 0; i < N; i++)
{
dp[i, 0] = 1;
}
// Traverse the range [1, R - L]
for(int i = 1; i < dp.GetLength(1); i++)
{
// Update dp[i][j]
dp[0, i] = dp[0, i - 1] + 1;
}
// Assign dp[0][R-L] to ans
ans = dp[0, R - L];
// Traverse the range [1, N]
for(int i = 1; i < N; i++)
{
// Traverse the range [1, R - L]
for(int j = 1; j < dp.GetLength(1); j++)
{
// Update dp[i][j]
dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
}
// Increment ans by dp[i-1][j]
ans += dp[i, R - L];
}
// Return ans
return ans;
}
// Driver Code
public static void Main()
{
// Input
int N = 3;
int L = 6;
int R = 9;
// Function call
Console.Write(Count(N, L, R));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to count total number of ways
function Count(N, L, R) {
// Stores all DP-states
let dp = new Array(N).fill(0).map(() => new Array(R - L + 1).fill(0));
// Stores the result
let ans = 0;
// Traverse the range [0, N]
for (let i = 0; i < N; i++) {
dp[i][0] = 1;
}
// Traverse the range [1, R - L]
for (let i = 1; i < dp[0].length; i++) {
// Update dp[i][j]
dp[0][i] = dp[0][i - 1] + 1;
}
// Assign dp[0][R-L] to ans
ans = dp[0][R - L];
// Traverse the range [1, N]
for (let i = 1; i < N; i++) {
// Traverse the range [1, R - L]
for (let j = 1; j < dp[0].length; j++) {
// Update dp[i][j]
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
// Increment ans by dp[i-1][j]
ans += dp[i][R - L];
}
// Return ans
return ans;
}
// Driver Code
// Input
let N = 3;
let L = 6;
let R = 9;
// Function call
document.write(Count(N, L, R));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
34
Complejidad de Tiempo: O(N * (R – L))
Espacio Auxiliar: O(N * (R – L))
Publicación traducida automáticamente
Artículo escrito por AshishKumarSharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA