in

Algoritmo de valla de pintura – GeeksforGeeks

gfg 200x200 min

Dada una cerca con n postes yk colores, averigüe la cantidad de formas de pintar la cerca de modo que como máximo 2 postes adyacentes tengan el mismo color. Dado que la respuesta puede ser grande, devuélvala módulo 10 ^ 9 + 7.
Ejemplos:

Input : n = 2 k = 4
Output : 16
We have 4 colors and 2 posts.
Ways when both posts have same color : 4 
Ways when both posts have diff color :
4(choices for 1st post) * 3(choices for 
2nd post) = 12

Input : n = 3 k = 2
Output : 6

La siguiente imagen muestra las 6 formas posibles de pintar 3 postes con 2 colores:

painting fence 1

Considere la siguiente imagen en la que c, c ‘y c ”son los colores respectivos de las publicaciones i, i-1 e i -2.

painting fence 2

De acuerdo con la restricción del problema, c = c ‘= c ”no es posible simultáneamente, entonces c’! = C o c”! = Co ambos. Hay k – 1 posibilidades para c ‘! = Cyk – 1 para c ”! = C.

 diff = no of ways when color of last
        two posts is different
 same = no of ways when color of last 
        two posts is same
 total ways = diff + sum

for n = 1
    diff = k, same = 0
    total = k

for n = 2
    diff = k * (k-1) //k choices for
           first post, k-1 for next
    same = k //k choices for common 
           color of two posts
    total = k +  k * (k-1)

for n = 3
    diff = k * (k-1)* (k-1) 
           //(k-1) choices for the first place 
        // k choices for the second place
        //(k-1) choices for the third place
    same = k * (k-1) * 2
        // 2 is multiplied because consider two color R and B
        // R R B or B R R 
        // B B R or R B B  
           c'' != c, (k-1) choices for it

Hence we deduce that,
total[i] = same[i] + diff[i]
same[i]  = diff[i-1]
diff[i]  = (diff[i-1] + diff[i-2]) * (k-1)
         = total[i-1] * (k-1)

A continuación se muestra la implementación del problema:

C ++

#include <bits/stdc++.h>

using namespace std;

long countWays(int n, int k)

{

    long dp[n + 1];

    memset(dp, 0, sizeof(dp));

    long long mod = 1000000007;

    dp[1] = k;

    dp[2] = k * k;

    for (int i = 3; i <= n; i++) {

        dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod;

    }

    return dp[n];

}

int main()

{

    int n = 3, k = 2;

    cout << countWays(n, k) << endl;

    return 0;

}

Java

import java.util.*;

class GfG {

    

    

    static long countWays(int n, int k)

    {

        

        long dp[] = new long[n + 1];

        Arrays.fill(dp, 0);

        int mod = 1000000007;

        

        dp[1] = k;

        

        

        

        int same = 0, diff = k;

        

        for (int i = 2; i <= n; i++) {

            

            same = diff;

            

            diff = (int) (dp[i - 1] * (k - 1));

            diff = diff % mod;

            

            dp[i] = (same + diff) % mod;

        }

        return dp[n];

    }

    

    public static void main(String[] args)

    {

        int n = 3, k = 2;

        System.out.println(countWays(n, k));

    }

}

Python3

def countWays(n, k):

    

    dp = [0] * (n + 1)

    total = k

    mod = 1000000007

    

    dp[1] = k

    dp[2] = k * k   

    

    for i in range(3,n+1):

        dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod

        

    return dp[n]

  

n = 3

k = 2

print(countWays(n, k))

 

C#

using System;

public class GFG

{

  

  

  static long countWays(int n, int k)

  {

    

    long[] dp = new long[n + 1];

    Array.Fill(dp, 0);

    int mod = 1000000007;

    

    dp[1] = k;

    

    

    

    int same = 0, diff = k;

    

    for (int i = 2; i <= n; i++)

    {

      

      same = diff;

      

      diff = (int)(dp[i - 1] * (k - 1));

      diff = diff % mod;

      

      dp[i] = (same + diff) % mod;

    }

    return dp[n];

  }

  

  static public void Main ()

  {

    int n = 3, k = 2;

    Console.WriteLine(countWays(n, k));

  }

}

Javascript

<script>

    

    

    

    

    function countWays(n, k)

    {

      

      let dp = new Array(n + 1);

      dp.fill(0);

      let mod = 1000000007;

      

      dp[1] = k;

      

      

      

      let same = 0, diff = k;

      

      for (let i = 2; i <= n; i++)

      {

        

        same = diff;

        

        diff = (dp[i - 1] * (k - 1));

        diff = diff % mod;

        

        dp[i] = (same + diff) % mod;

      }

      return dp[n];

    }

    

    let n = 3, k = 2;

    document.write(countWays(n, k));

    

    

</script>

Producción:

6

Optimización del espacio:
Podemos optimizar la solución anterior para usar una variable en lugar de una tabla.
A continuación se muestra la implementación del problema:

C ++

#include <bits/stdc++.h>

using namespace std;

long countWays(int n, int k)

{

    

    long total = k;

    int mod = 1000000007;

    

    

    

    int same = 0, diff = k;

    

    for (int i = 2; i <= n; i++) {

        

        same = diff;

        

        diff = total * (k - 1);

        diff = diff % mod;

        

        total = (same + diff) % mod;

    }

    return total;

}

int main()

{

    int n = 3, k = 2;

    cout << countWays(n, k) << endl;

    return 0;

}

Java

class GFG {

    

    

    static long countWays(int n, int k)

    {

        

        long total = k;

        int mod = 1000000007;

        

        

        

        int same = 0, diff = k;

        

        for (int i = 2; i <= n; i++) {

            

            same = diff;

            

            diff = (int)total * (k - 1);

            diff = diff % mod;

            

            total = (same + diff) % mod;

        }

        return total;

    }

    

    public static void main(String[] args)

    {

        int n = 3, k = 2;

        System.out.println(countWays(n, k));

    }

}

Python3

def countWays(n, k) :

    

    total = k

    mod = 1000000007

    

    

    

    same, diff = 0, k

    

    for i in range(2, n + 1) :

        

        

        

        same = diff

        

        

        diff = total * (k - 1)

        diff = diff % mod

        

        total = (same + diff) % mod

    

    return total

if __name__ == "__main__" :

    n, k = 3, 2

    print(countWays(n, k))

C#

using System;

class GFG {

    

    

    static long countWays(int n, int k)

    {

        

        long total = k;

        int mod = 1000000007;

        

        

        

        long same = 0, diff = k;

        

        for (int i = 2; i <= n; i++) {

            

            same = diff;

            

            diff = total * (k - 1);

            diff = diff % mod;

            

            total = (same + diff) % mod;

        }

        return total;

    }

    

    static void Main()

    {

        int n = 3, k = 2;

        Console.Write(countWays(n, k));

    }

}

PHP

<?php

function countWays($n, $k)

{

    

    $total = $k;

    $mod = 1000000007;

    

    

    

    $same = 0;

    $diff = $k;

    

    for ($i = 2; $i <= $n; $i++)

    {

        

        $same = $diff;

        

        $diff = $total * ($k - 1);

        $diff = $diff % $mod;

        

        $total = ($same + $diff) % $mod;

    }

    return $total;

}

$n = 3;

$k = 2;

echo countWays($n, $k) . "n";

?>

Javascript

<script>

    

    

    

    

    function countWays(n, k)

    {

        

        let total = k;

        let mod = 1000000007;

 

        

        

        

        let same = 0, diff = k;

 

        

        for (let i = 2; i <= n; i++) {

            

            same = diff;

 

            

            diff = total * (k - 1);

            diff = diff % mod;

 

            

            total = (same + diff) % mod;

        }

 

        return total;

    }

    

    let n = 3, k = 2;

      document.write(countWays(n, k));

        

</script>

Producción:

6

Este artículo es una contribución de Aditi Sharma. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o envíe su artículo por correo electrónico a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

¡Atención lector! No dejes de aprender ahora. Obtenga todos los conceptos importantes de DSA con el Curso autodidacta de DSA a un precio asequible para los estudiantes y prepárese para la industria. Para completar su preparación desde el aprendizaje de un idioma hasta DS Algo y muchos más, consulte Curso completo de preparación para entrevistas.

En caso de que desee asistir clases en vivo con expertos, consulte Clases en vivo de DSA para profesionales que trabajan y Programación competitiva en vivo para estudiantes.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

apple touch icon@2

fecha: convierte una marca de tiempo de Unix a la hora en JavaScript

edit

Prisión vs cárcel: diferencia y comparación