Hay una calle de longitud n y como sabemos tiene dos lados. Por lo tanto, hay un total de 2 * n plazas disponibles. En cada uno de estos lugares se puede construir una casa o una oficina con las siguientes 2 restricciones:
1. No pueden ser contiguas dos oficinas del mismo lado de la calle.
2. Dos oficinas en diferentes lados de la calle no pueden estar exactamente opuestas, es decir, no pueden pasarse por alto.
No hay restricciones para construir casas y cada lugar debe tener una casa u oficina.
Dada la longitud de la calle n, encuentre el número total de formas de construir la calle.
Ejemplos:
Input : 2 Output : 7 Please see below diagram for explanation. Input : 3 Output : 17
La siguiente imagen muestra las 7 formas posibles de construir la calle con N = 2
Ways for building street with length 1
with 2 houses: (H H) = {1}
with 1 office and 1 house: (O H) (H O) = {2}
(O O) is not allowed according to the problem statement.
Total = 1 + 2 = 3
For length = 2,
with 2 houses: (H H) can be added to all
the cases of length 1:
(H H) (H H) (H H)
(H H) (O H) (H O) = {3}
with 1 office and 1 house:
(O H) and (H O) can both be added to all
the cases of length 1 with last row (H H)
(O H) (H O)
(H H) (H H) = {2}
when last row of a case of length 1
contains 1 office, it can only be
extended in one way to build an office
in row 2.
(H O) (O H)
(O H) (H O) = {2}
(O H) (H O) (O O)
(O H) (H O) (O H) etc are not allowed.
Total = 3 + 2 + 2 = 7
Dado que el problema se puede resolver encontrando soluciones para subproblemas más pequeños y luego extendiendo la misma lógica, se puede resolver mediante programación dinámica. Nos movemos en pasos de una unidad de longitud. Para cada fila tenemos dos opciones:
Construir casas en ambos lugares
Construir una casa y una oficina
La primera se puede hacer sin restricciones. Hay una forma de construir casas en ambos lugares en longitud i. Entonces, formas totales usando esta opción = formas totales para la longitud i – 1.
Para la segunda opción, si la fila (i-1) tuviera casas en ambos lugares, tenemos dos formas de construir una oficina, es decir, (HO) y (OH)
si la fila (i-1) tuviera una oficina en uno de sus dos lugares, solo tenemos una forma de construir una oficina en la fila i. Si la fila anterior tuviera (OH) la fila actual tendría (HO) y de manera similar para la fila anterior = ( HO) fila actual = (OH).
De la lógica anterior, formas totales con esta elección = 2 * (elección1(i-1)) + elección2(i-1)
Construiremos un dp 2D para esto.
dp[0][i] indica opción1 y dp[1][i] indica opción2 para la fila i.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to count ways to build street
// under given constraints
#include <bits/stdc++.h>
using namespace std;
// function to count ways of building
// a street of n rows
long countWays(int n)
{
long dp[2][n + 1];
// base case
dp[0][1] = 1;
dp[1][1] = 2;
for (int i = 2; i <= n; i++) {
// ways of building houses in both
// the spots of ith row
dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
// ways of building an office in one of
// the two spots of ith row
dp[1][i] = dp[0][i - 1] * 2 + dp[1][i - 1];
}
// total ways for n rows
return dp[0][n] + dp[1][n];
}
// driver program for checking above function
int main()
{
int n = 5;
cout << "Total no of ways with n = " << n
<< " are: " << countWays(n) << endl;
}
Java
// Java program to count ways to build street
// under given constraints
public class GFG {
// function to count ways of building
// a street of n rows
static long countWays(int n) {
long dp[][] = new long[2][n + 1];
// base case
dp[0][1] = 1;
dp[1][1] = 2;
for (int i = 2; i <= n; i++) {
// ways of building houses in both
// the spots of ith row
dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
// ways of building an office in one of
// the two spots of ith row
dp[1][i] = dp[0][i - 1] * 2 + dp[1][i - 1];
}
// total ways for n rows
return dp[0][n] + dp[1][n];
}
// driver program for checking above function
public static void main(String[] args) {
int n = 5;
System.out.print("Total no of ways with n = " + n
+ " are: " + countWays(n));
}
}
/*This code is contributed by PrinciRaj1992*/
Python3
# Python3 program to count ways to build
# street under given constraints
# function to count ways of building
# a street of n rows
def countWays(n) :
dp = [[0] * (n + 1) for i in range(2)]
# base case
dp[0][1] = 1
dp[1][1] = 2
for i in range(2, n + 1) :
# ways of building houses in both
# the spots of ith row
dp[0][i] = dp[0][i - 1] + dp[1][i - 1]
# ways of building an office in one of
# the two spots of ith row
dp[1][i] = (dp[0][i - 1] * 2 +
dp[1][i - 1])
# total ways for n rows
return dp[0][n] + dp[1][n]
# Driver Code
if __name__ == "__main__" :
n = 5
print("Total no of ways with n =",
n, "are:", countWays(n))
# This code is contributed by Ryuga
C#
// C# program to count ways to build street
// under given constraints
using System;
public class GFG{
// function to count ways of building
// a street of n rows
static long countWays(int n) {
long [,]dp = new long[2 , n + 1];
// base case
dp[0,1] = 1;
dp[1,1] = 2;
for (int i = 2; i <= n; i++) {
// ways of building houses in both
// the spots of ith row
dp[0 , i] = dp[0 , i - 1] + dp[1 , i - 1];
// ways of building an office in one of
// the two spots of ith row
dp[1 , i] = dp[0 , i - 1] * 2 + dp[1 , i - 1];
}
// total ways for n rows
return dp[0 , n] + dp[1 , n];
}
// driver program for checking above function
public static void Main() {
int n = 5;
Console.Write("Total no of ways with n = " + n
+ " are: " + countWays(n));
}
}
/*This code is contributed by PrinciRaj1992*/
PHP
<?php
// PHP program to count ways to build street
// under given constraints
// function to count ways of building
// a street of n rows
function countWays($n)
{
// base case
$dp[0][1] = 1;
$dp[1][1] = 2;
for ($i = 2; $i <= $n; $i++) {
// ways of building houses in both
// the spots of ith row
$dp[0][$i] = $dp[0][$i - 1] +
$dp[1][$i - 1];
// ways of building an office in one of
// the two spots of ith row
$dp[1][$i] = $dp[0][$i - 1] *
2 + $dp[1][$i - 1];
}
// total ways for n rows
return $dp[0][$n] + $dp[1][$n];
}
// Driver Code
$n = 5;
echo "Total no of ways with n = ",$n,
" are: " ,countWays($n),"\n";
// This code is contributed by jit_t
?>
Javascript
<script>
// Javascript program to count ways to
// build street under given constraints
// Function to count ways of building
// a street of n rows
function countWays(n)
{
let dp = new Array(2);
for(let i = 0; i < 2; i++)
{
dp[i] = new Array(n + 1);
}
// Base case
dp[0][1] = 1;
dp[1][1] = 2;
for(let i = 2; i <= n; i++)
{
// Ways of building houses in both
// the spots of ith row
dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
// Ways of building an office in one of
// the two spots of ith row
dp[1][i] = dp[0][i - 1] * 2 + dp[1][i - 1];
}
// Total ways for n rows
return dp[0][n] + dp[1][n];
}
// Driver code
let n = 5;
document.write("Total no of ways with n = " +
n + " are: " + countWays(n));
// This code is contributed by suresh07
</script>
Total no of ways with n = 5 are: 99
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Otro método
Suponga que tiene A(n-1) y A(n-2), donde A(i) representa formas para 2*i edificios, entonces:
A(n) = (Número de formas que tiene (HH) en A (n-1) )*3 + (Número de formas en que tiene (OH) en A(n-1))*2
¿Cómo surgen estos casos? Simplemente puede pensar en hacer 2 estados como se examinó en la explicación anterior.
Número de formas en que tiene (HH) en A (n-1) = Fijar HH en (n-1) ésima posición, esto es igual al número de formas de la posición n-2 (fijar n-1 en HH).
Número de formas que tiene (OH) en A(n-1) = (Número de formas en n-1) – (Número de formas de HH en la posición A(n-1)).
Entonces A(n) = 3*A(n-2) + 2*(A(n-1)-A(n-2)) = 2*A(n-1)+A(n-2)
C++
// C++ program of above approach
#include <iostream>
using namespace std;
// Program to count ways
int countways(long long n)
{
long long A[n+1];
A[0] = 1;
A[1] = 3;
A[2] = 7;
// Iterate from 2 to n
for(int i=2;i<=n;i++)
{
A[i] = 2*A[i-1]+A[i-2];
}
return A[n];
}
// Driver code
int main() {
int n = 5;
// Count Ways
cout << countways(5) << endl;
return 0;
}
Java
// Java program of above approach
import java.io.*;
class GFG{
// Program to count ways
static int countways(int n)
{
int [] A = new int[n+1];
A[0] = 1;
A[1] = 3;
A[2] = 7;
// Iterate from 2 to n
for(int i = 2; i <= n; i++)
{
A[i] = 2 * A[i - 1] + A[i - 2];
}
return A[n];
}
// Driver code
public static void main(String[] args)
{
int n = 5;
// Count Ways
System.out.println(countways(5));
}
}
// This code is contributed by Ankita saini
Python3
# Python3 program of above approach # Program to count ways def countways(n): A = [0 for i in range(n + 2)] A[0] = 1 A[1] = 3 A[2] = 7 # Iterate from 2 to n for i in range(2, n + 1): A[i] = 2 * A[i - 1] + A[i - 2] return A[n] # Driver code n = 5 # Count Ways print(countways(5)) # This code is contributed by Sanjit_Prasad
C#
// C# program of above approach
using System;
class GFG{
// Program to count ways
static int countways(int n)
{
int [] A = new int[n+1];
A[0] = 1;
A[1] = 3;
A[2] = 7;
// Iterate from 2 to n
for(int i = 2; i <= n; i++)
{
A[i] = 2 * A[i - 1] + A[i - 2];
}
return A[n];
}
// Driver code
public static void Main()
{
int n = 5;
// Count Ways
Console.Write(countways(n));
}
}
// This code is contributed by bunnyram19.
Javascript
<script>
// Javascript program of above approach
// Program to count ways
function countways(n)
{
let A = new Array(n+1).fill(0);
A[0] = 1;
A[1] = 3;
A[2] = 7;
// Iterate from 2 to n
for(let i=2;i<=n;i++)
{
A[i] = 2*A[i-1]+A[i-2];
}
return A[n];
}
// driver program
let n = 5;
// Count Ways
document.write(countways(5))
</script>
99
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
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 enviar tu artículo por correo 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 tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA