Dados tres números enteros N , M y K . La tarea es encontrar el número de formas de llenar N posiciones usando M colores de modo que haya exactamente K pares de diferentes colores adyacentes.
Ejemplos:
Entrada: N = 3, M = 2, K = 1
Salida: 4
Sean los colores 1 y 2, entonces las formas son:
1, 1, 2
1, 2, 2
2, 2, 1
2, 1, 1
El Las 4 formas anteriores tienen exactamente un par de elementos adyacentes con diferentes colores.Entrada: N = 3, M = 3, K = 2
Salida: 12
Enfoque: podemos usar la programación dinámica con memorización para resolver el problema anterior. Hay N posiciones para llenar, por lo tanto, la función recursiva estará compuesta por dos llamadas, una si la siguiente posición se llena con el mismo color y la otra si se llena con un color diferente. Por lo tanto, las llamadas recursivas serán:
- countWays(index + 1, cnt) , si el siguiente índice se rellena con el mismo color.
- (m – 1) * countWays(index + 1, cnt + 1) , si el siguiente índice se rellena con un color diferente. El número de vías se multiplica por (m – 1) .
Los casos básicos serán:
- Si index = n , entonces se realiza una verificación del valor de cnt . Si cnt = K , entonces es una forma posible, por lo tanto, devuelve 1 , de lo contrario, devuelve 0 .
- Para evitar llamadas repetitivas, memorice el valor devuelto en una array 2-D y devuelva este valor si la llamada recursiva con los mismos parámetros se realiza nuevamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define max 4
// Recursive function to find the required number of ways
int countWays(int index, int cnt, int dp[][max], int n, int m, int k)
{
// When all positions are filled
if (index == n) {
// If adjacent pairs are exactly K
if (cnt == k)
return 1;
else
return 0;
}
// If already calculated
if (dp[index][cnt] != -1)
return dp[index][cnt];
int ans = 0;
// Next position filled with same color
ans += countWays(index + 1, cnt, dp, n, m, k);
// Next position filled with different color
// So there can be m-1 different colors
ans += (m - 1) * countWays(index + 1, cnt + 1, dp, n, m, k);
return dp[index][cnt] = ans;
}
// Driver Code
int main()
{
int n = 3, m = 3, k = 2;
int dp[n + 1][max];
memset(dp, -1, sizeof dp);
cout << m * countWays(1, 0, dp, n, m, k);
}
Java
//Java implementation of the approach
class solution
{
static final int max=4;
// Recursive function to find the required number of ways
static int countWays(int index, int cnt, int dp[][], int n, int m, int k)
{
// When all positions are filled
if (index == n) {
// If adjacent pairs are exactly K
if (cnt == k)
return 1;
else
return 0;
}
// If already calculated
if (dp[index][cnt] != -1)
return dp[index][cnt];
int ans = 0;
// Next position filled with same color
ans += countWays(index + 1, cnt, dp, n, m, k);
// Next position filled with different color
// So there can be m-1 different colors
ans += (m - 1) * countWays(index + 1, cnt + 1, dp, n, m, k);
return dp[index][cnt] = ans;
}
// Driver Code
public static void main(String args[])
{
int n = 3, m = 3, k = 2;
int dp[][]= new int [n + 1][max];
for(int i=0;i<n+1;i++)
for(int j=0;j<max;j++)
dp[i][j]=-1;
System.out.println(m * countWays(1, 0, dp, n, m, k));
}
}
//contributed by Arnab Kundu
Python 3
# Python 3 implementation of the approach max = 4 # Recursive function to find the # required number of ways def countWays(index, cnt, dp, n, m, k): # When all positions are filled if (index == n) : # If adjacent pairs are exactly K if (cnt == k): return 1 else: return 0 # If already calculated if (dp[index][cnt] != -1): return dp[index][cnt] ans = 0 # Next position filled with same color ans += countWays(index + 1, cnt, dp, n, m, k) # Next position filled with different color # So there can be m-1 different colors ans += (m - 1) * countWays(index + 1, cnt + 1, dp, n, m, k) dp[index][cnt] = ans return dp[index][cnt] # Driver Code if __name__ == "__main__": n = 3 m = 3 k = 2 dp = [[-1 for x in range(n + 1)] for y in range(max)] print(m * countWays(1, 0, dp, n, m, k)) # This code is contributed by ita_c
C#
// C# implementation of the approach
using System;
class solution
{
static int max=4;
// Recursive function to find the required number of ways
static int countWays(int index, int cnt, int [,]dp, int n, int m, int k)
{
// When all positions are filled
if (index == n) {
// If adjacent pairs are exactly K
if (cnt == k)
return 1;
else
return 0;
}
// If already calculated
if (dp[index,cnt] != -1)
return dp[index,cnt];
int ans = 0;
// Next position filled with same color
ans += countWays(index + 1, cnt, dp, n, m, k);
// Next position filled with different color
// So there can be m-1 different colors
ans += (m - 1) * countWays(index + 1, cnt + 1, dp, n, m, k);
return dp[index,cnt] = ans;
}
// Driver Code
public static void Main()
{
int n = 3, m = 3, k = 2;
int [,]dp= new int [n + 1,max];
for(int i=0;i<n+1;i++)
for(int j=0;j<max;j++)
dp[i,j]=-1;
Console.WriteLine(m * countWays(1, 0, dp, n, m, k));
}
// This code is contributed by Ryuga
}
PHP
<?php
// PHP implementation of the approach
$GLOBALS['max'] = 4;
// Recursive function to find the
// required number of ways
function countWays($index, $cnt, $dp,
$n, $m, $k)
{
// When all positions are filled
if ($index == $n)
{
// If adjacent pairs are exactly K
if ($cnt == $k)
return 1;
else
return 0;
}
// If already calculated
if ($dp[$index][$cnt] != -1)
return $dp[$index][$cnt];
$ans = 0;
// Next position filled with same color
$ans += countWays($index + 1, $cnt,
$dp, $n, $m, $k);
// Next position filled with different color
// So there can be m-1 different colors
$ans += ($m - 1) * countWays($index + 1, $cnt + 1,
$dp, $n, $m, $k);
$dp[$index][$cnt] = $ans;
return $dp[$index][$cnt];
}
// Driver Code
$n = 3;
$m = 3;
$k = 2;
$dp = array(array());
for($i = 0; $i < $n + 1; $i++)
for($j = 0; $j < $GLOBALS['max']; $j++)
$dp[$i][$j] = -1;
echo $m * countWays(1, 0, $dp, $n, $m, $k);
// This code is contributed by aishwarya.27
?>
Javascript
<script>
//Javascript implementation of the approach
let max=4;
// Recursive function to find the required number of ways
function countWays(index,cnt,dp,n,m,k)
{
// When all positions are filled
if (index == n) {
// If adjacent pairs are exactly K
if (cnt == k)
return 1;
else
return 0;
}
// If already calculated
if (dp[index][cnt] != -1)
return dp[index][cnt];
let ans = 0;
// Next position filled with same color
ans += countWays(index + 1, cnt, dp, n, m, k);
// Next position filled with different color
// So there can be m-1 different colors
ans += (m - 1) * countWays(index + 1, cnt + 1, dp, n, m, k);
return dp[index][cnt] = ans;
}
// Driver Code
let n = 3, m = 3, k = 2;
let dp=new Array(n+1);
for(let i=0;i<n+1;i++)
{
dp[i]=new Array(max);
for(let j=0;j<max;j++)
dp[i][j]=-1;
}
document.write(m * countWays(1, 0, dp, n, m, k));
// This code is contributed by rag2127
</script>
Producción:
12
Complejidad Temporal: O(n*4), ya que estamos usando recursividad y la función se llamará N veces, donde N es el número de puestos a cubrir.
Espacio Auxiliar: O(n*4), ya que estamos usando espacio extra para la array dp, donde N es el número de puestos a cubrir.