Hay n escaleras, una persona parada en la parte inferior quiere llegar a la cima. La persona puede subir 1 o 2 escalones a la vez. Cuente el número de formas en que la persona puede llegar a la cima.
Considere el ejemplo que se muestra en el diagrama. El valor de n es 3. Hay 3 formas de llegar a la cima. El diagrama está tomado de los rompecabezas de Fibonacci más fáciles.
Ejemplos:
Input: n = 1 Output: 1 There is only one way to climb 1 stair Input: n = 2 Output: 2 There are two ways: (1, 1) and (2) Input: n = 4 Output: 5 (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)
Método 1 : El primer método utiliza la técnica de la recursividad para resolver este problema.
Enfoque: podemos encontrar fácilmente la naturaleza recursiva en el problema anterior. La persona puede llegar al escalón n desde (n-1) este escalón o desde (n-2) este escalón . Por lo tanto, para cada escalón n , tratamos de encontrar el número de formas de llegar al n-1 escalón y al n-2 escalón y las sumamos para dar la respuesta para el n -ésimo escalón . Por lo tanto, la expresión para tal enfoque resulta ser:
ways(n) = ways(n-1) + ways(n-2)
La expresión anterior es en realidad la expresión de los números de Fibonacci , pero hay una cosa a tener en cuenta, el valor deways(n) es igual a fibonacci(n+1).
ways(1) = fib(2) = 1 ways(2) = fib(3) = 2 ways(3) = fib(4) = 3
Para una mejor comprensión, consultemos el árbol de recursión a continuación:
Input: N = 4
fib(5)
'3' / \ '2'
/ \
fib(4) fib(3)
'2' / \ '1' / \
/ \ / \
fib(3) fib(2)fib(2) fib(1)
/ \ '1' / \ '0'
'1' / '1'\ / \
/ \ fib(1) fib(0)
fib(2) fib(1)
Entonces podemos usar la función para los números de Fibonacci para encontrar el valor de las vías (n). A continuación se muestra la implementación en C++ de la idea anterior.
C++
// C++ program to count number of
// ways to reach Nth stair
#include <bits/stdc++.h>
using namespace std;
// A simple recursive program to
// find N'th fibonacci number
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to
// reach s'th stair
int countWays(int s)
{
return fib(s + 1);
}
// Driver C
int main()
{
int s = 4;
cout << "Number of ways = " << countWays(s);
return 0;
}
// This code is contributed by shubhamsingh10
C
// C Program to count number of
// ways to reach Nth stair
#include <stdio.h>
// A simple recursive program to
// find n'th fibonacci number
int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to reach s'th stair
int countWays(int s)
{
return fib(s + 1);
}
// Driver program to test above functions
int main()
{
int s = 4;
printf("Number of ways = %d", countWays(s));
getchar();
return 0;
}
Java
class stairs {
// A simple recursive program to find
// n'th fibonacci number
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways to reach s'th stair
static int countWays(int s)
{
return fib(s + 1);
}
/* Driver program to test above function */
public static void main(String args[])
{
int s = 4;
System.out.println("Number of ways = " + countWays(s));
}
} /* This code is contributed by Rajat Mishra */
Python
# Python program to count # ways to reach nth stair # Recursive function to find # Nth fibonacci number def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # Returns no. of ways to # reach sth stair def countWays(s): return fib(s + 1) # Driver program s = 4 print "Number of ways = ", print countWays(s) # Contributed by Harshit Agrawal
C#
// C# program to count the
// number of ways to reach
// n'th stair
using System;
class GFG {
// A simple recursive
// program to find n'th
// fibonacci number
static int fib(int n)
{
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}
// Returns number of ways
// to reach s'th stair
static int countWays(int s)
{
return fib(s + 1);
}
// Driver Code
static public void Main()
{
int s = 4;
Console.WriteLine("Number of ways = " + countWays(s));
}
}
// This code is contributed
// by akt_mit
PHP
<?php
// A PHP program to count
// number of ways to reach
// n'th stair when a person
// can climb 1, 2, ..m stairs
// at a time.
// A simple recursive
// function to find n'th
// fibonacci number
function fib($n)
{
if ($n <= 1)
return $n;
return fib($n - 1) +
fib($n - 2);
}
// Returns number of
// ways to reach s'th stair
function countWays($s)
{
return fib($s + 1);
}
// Driver Code
$s = 4;
echo "Number of ways = ",
countWays($s);
// This code is contributed
// by m_kit
?>
Javascript
<script>
// A Javascript program to count
// number of ways to reach
// n'th stair when a person
// can climb 1, 2, ..m stairs
// at a time.
// A simple recursive
// function to find n'th
// fibonacci number
function fib(n)
{
if (n <= 1)
return n;
return fib(n - 1) +
fib(n - 2);
}
// Returns number of
// ways to reach s'th stair
function countWays(s)
{
return fib(s + 1);
}
// Driver Code
let s = 4;
document.write("Number of ways = " + countWays(s));
// This code is contributed
// by _saurabh_jaiswal
</script>
Producción
Number of ways = 5
Análisis de Complejidad:
- Complejidad de tiempo: O(2^n)
La complejidad de tiempo de la implementación anterior es exponencial (proporción áurea elevada a potencia n) debido a cálculos redundantes. Se puede optimizar para trabajar en tiempo O(Logn) usando las optimizaciones de funciones de Fibonacci discutidas anteriormente . - Espacio Auxiliar: O(1)
Generalización del Problema
Cómo contar el número de caminos si la persona puede subir hasta m escaleras para un valor dado m. Por ejemplo, si m es 4, la persona puede subir 1 escalón o 2 escalones o 3 escalones o 4 escalones a la vez.
Enfoque: Para la generalización del enfoque anterior, se puede utilizar la siguiente relación recursiva.
ways(n, m) = ways(n-1, m) + ways(n-2, m) + ... ways(n-m, m)
En este enfoque para alcanzar el escalón n , intente subir todo el número posible de peldaños menor que igual a n desde el escalón actual .
A continuación se muestra la implementación de la recurrencia anterior.
C++
// C++ program to count number of ways
// to reach nth stair when a person
// can climb either 1 or 2 stairs at a time
#include <bits/stdc++.h>
using namespace std;
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
if (n <= 1)
{
return n;
}
int res = 0;
for(int i = 1; i <= m && i <= n; i++)
{
res += countWaysUtil(n - i, m);
}
return res;
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver code
int main()
{
int s = 4, m = 2;
cout << "Number of ways = " << countWays(s, m);
return 0;
}
// This code is contribute by shubhamsingh10
C
// C program to count number of ways
// to reach nth stair when a person
// can climb either 1 or 2 stairs at a time
#include <stdio.h>
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
if (n <= 1)
return n;
int res = 0;
for (int i = 1; i <= m && i <= n; i++)
res += countWaysUtil(n - i, m);
return res;
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver program to test above functions-
int main()
{
int s = 4, m = 2;
printf("Number of ways = %d", countWays(s, m));
return 0;
}
Java
class stairs {
// A recursive function used by countWays
static int countWaysUtil(int n, int m)
{
if (n <= 1)
return n;
int res = 0;
for (int i = 1; i <= m && i <= n; i++)
res += countWaysUtil(n - i, m);
return res;
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
/* Driver program to test above function */
public static void main(String args[])
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
} /* This code is contributed by Rajat Mishra */
Python
# A program to count the number of ways # to reach n'th stair # Recursive function used by countWays def countWaysUtil(n, m): if n <= 1: return n res = 0 i = 1 while i<= m and i<= n: res = res + countWaysUtil(n-i, m) i = i + 1 return res # Returns number of ways to reach s'th stair def countWays(s, m): return countWaysUtil(s + 1, m) # Driver program s, m = 4, 2 print "Number of ways =", countWays(s, m) # Contributed by Harshit Agrawal
C#
using System;
public class stairs
{
// A recursive function used by countWays
static int countWaysUtil(int n, int m)
{
if (n <= 1)
return n;
int res = 0;
for (int i = 1; i <= m && i <= n; i++)
res += countWaysUtil(n - i, m);
return res;
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
/* Driver program to test above function */
public static void Main(String []args)
{
int s = 4, m = 2;
Console.WriteLine("Number of ways = "
+ countWays(s, m));
}
}
// This code is contributed by umadevi9616
PHP
<?php
// A PHP program to count
// number of ways to reach
// n'th stair when a person
// can climb either 1 or 2
// stairs at a time
// A recursive function
// used by countWays
function countWaysUtil($n, $m)
{
if ($n <= 1)
return $n;
$res = 0;
for ($i = 1; $i <= $m &&
$i <= $n; $i++)
$res += countWaysUtil($n - $i, $m);
return $res;
}
// Returns number of ways
// to reach s'th stair
function countWays($s, $m)
{
return countWaysUtil($s + 1, $m);
}
// Driver Code
$s = 4; $m = 2;
echo "Number of ways = ",
countWays($s, $m);
// This code is contributed
// by akt_mit
?>
Javascript
<script>
// A Javascript program to count
// number of ways to reach
// n'th stair when a person
// can climb either 1 or 2
// stairs at a time
// A recursive function
// used by countWays
function countWaysUtil(n, m)
{
if (n <= 1)
return n;
let res = 0;
for (let i = 1; i <= m &&
i <= n; i++)
res += countWaysUtil(n - i, m);
return res;
}
// Returns number of ways
// to reach s'th stair
function countWays(s, m)
{
return countWaysUtil(s + 1, m);
}
// Driver Code
let s = 4;
let m = 2;
document.write("Number of ways = " + countWays(s, m));
// This code is contributed by _saurabh_jaiswal
</script>
Producción
Number of ways = 5
Análisis de Complejidad:
- Complejidad de tiempo: O(2^n)
La complejidad de tiempo de la implementación anterior es exponencial (proporción áurea elevada a potencia n) debido a cálculos redundantes. Se puede optimizar a O(m*n) usando programación dinámica. - Espacio Auxiliar: O(1)
Método 2: Memoización
También podemos usar el enfoque ascendente de dp para resolver este problema
Para esto, podemos crear una array dp[] e inicializarla con -1.
Siempre que veamos que un subproblema no se resuelve podemos llamar al método recursivo,
de lo contrario, detenemos la recursividad si el subproblema ya está resuelto.
C++
// C++ program to count number of ways to reach Nth stair
#include <bits/stdc++.h>
using namespace std;
// A simple recursive program to find N'th fibonacci number
int fib(int n, int dp[])
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
return dp[n];
}
// Returns number of ways to reach s'th stair
int countWays(int n)
{
int dp[n + 1];
memset(dp, -1, sizeof dp);
fib(n, dp);
return dp[n];
}
// Driver C
int main()
{
int n = 4;
cout << "Number of ways = " << countWays(n);
return 0;
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
C
// C program to count number of ways to reach Nth stair
#include <stdio.h>
#include <string.h>
// A simple recursive program to find N'th fibonacci number
int fib(int n, int dp[])
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
return dp[n];
}
// Returns number of ways to reach s'th stair
int countWays(int n)
{
int dp[n + 1];
memset(dp, -1, sizeof dp);
fib(n, dp);
return dp[n];
}
// Driver C
int main()
{
int n = 4;
printf("Number of ways = %d", countWays(n));
return 0;
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
Java
// Java program to count number of
// ways to reach Nth stair
class GFG
{
// A simple recursive program to
// find N'th fibonacci number
static int fib(int n, int dp[])
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
return dp[n];
}
// Returns number of ways to
// reach s'th stair
static int countWays(int n)
{
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
dp[i] = -1;
}
fib(n, dp);
return dp[n];
}
// Driver code
public static void main(String[] args)
{
int n = 4;
System.out.println(countWays(n));
}
}
// This code is contributed by Karandeep1234
Python3
# Python program to count number of
# ways to reach Nth stair
# A simple recursive program to
# find N'th fibonacci number
def fib(n, dp):
if (n <= 1):
return 1
if(dp[n] != -1 ):
return dp[n]
dp[n] = fib(n - 1, dp) + fib(n - 2, dp)
return dp[n]
# Returns number of ways to
# reach s'th stair
def countWays(n):
dp = [-1 for i in range(n + 1)]
fib(n, dp)
return dp[n]
# Driver Code
n = 4
print("Number of ways = " + str(countWays(n)))
# This code is contributed by shinjanpatra
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// A simple recursive program to
// find N'th fibonacci number
static int fib(int n, int[] dp)
{
if (n <= 1)
return dp[n] = 1;
if (dp[n] != -1) {
return dp[n];
}
dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
return dp[n];
}
// Returns number of ways to
// reach s'th stair
static int countWays(int n)
{
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
dp[i] = -1;
}
fib(n, dp);
return dp[n];
}
// Driver Code
public static void Main()
{
int n = 4;
Console.Write("Number of ways = " + countWays(n));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript program to count number of
// ways to reach Nth stair
// A simple recursive program to
// find N'th fibonacci number
function fib(n, dp)
{
if (n <= 1)
return dp[n] = 1;
if(dp[n] != -1 ){
return dp[n] ;
}
dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
return dp[n] ;
}
// Returns number of ways to
// reach s'th stair
function countWays(n)
{
let dp = new Array(n+1).fill(-1) ;
fib(n, dp) ;
return dp[n] ;
}
// Driver Code
let n = 4;
document.write("Number of ways = " + countWays(n));
// This code is contributed by shinjanpatra.
</script>
Producción
Number of ways = 5
Análisis de Complejidad:
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Método 3 : Este método utiliza la técnica de Programación Dinámica para llegar a la solución.
Enfoque: creamos una tabla res[] de forma ascendente usando la siguiente relación:
res[i] = res[i] + res[i-j] for every (i-j) >= 0
tal que el i -ésimo índice de la array contendrá el número de caminos requeridos para alcanzar el i -ésimo paso considerando todas las posibilidades de ascenso (es decir, de 1 a i ).
El siguiente código implementa el enfoque anterior:
C++
// C++ program to count number of ways
// to reach n'th stair when a person
// can climb 1, 2, ..m stairs at a time
#include <iostream>
using namespace std;
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
int res[n];
res[0] = 1;
res[1] = 1;
for(int i = 2; i < n; i++)
{
res[i] = 0;
for(int j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver code
int main()
{
int s = 4, m = 2;
cout << "Number of ways = "
<< countWays(s, m);
return 0;
}
// This code is contributed by shubhamsingh10
C
// A C program to count number of ways
// to reach n'th stair when
// a person can climb 1, 2, ..m stairs at a time
#include <stdio.h>
// A recursive function used by countWays
int countWaysUtil(int n, int m)
{
int res[n];
res[0] = 1;
res[1] = 1;
for (int i = 2; i < n; i++) {
res[i] = 0;
for (int j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways to reach s'th stair
int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver program to test above functions
int main()
{
int s = 4, m = 2;
printf("Number of ways = %d", countWays(s, m));
return 0;
}
Java
// Java program to count number of ways
// to reach n't stair when a person
// can climb 1, 2, ..m stairs at a time
class GFG {
// A recursive function used by countWays
static int countWaysUtil(int n, int m)
{
int res[] = new int[n];
res[0] = 1;
res[1] = 1;
for (int i = 2; i < n; i++) {
res[i] = 0;
for (int j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver method
public static void main(String[] args)
{
int s = 4, m = 2;
System.out.println("Number of ways = "
+ countWays(s, m));
}
}
Python
# A program to count the number of # ways to reach n'th stair # Recursive function used by countWays def countWaysUtil(n, m): # Creates list res with all elements 0 res = [0 for x in range(n)] res[0], res[1] = 1, 1 for i in range(2, n): j = 1 while j<= m and j<= i: res[i] = res[i] + res[i-j] j = j + 1 return res[n-1] # Returns number of ways to reach s'th stair def countWays(s, m): return countWaysUtil(s + 1, m) # Driver Program s, m = 4, 2 print "Number of ways =", countWays(s, m) # Contributed by Harshit Agrawal
C#
// C# program to count number
// of ways to reach n'th stair when
// a person can climb 1, 2, ..m
// stairs at a time
using System;
class GFG {
// A recursive function
// used by countWays
static int countWaysUtil(int n, int m)
{
int[] res = new int[n];
res[0] = 1;
res[1] = 1;
for (int i = 2; i < n; i++) {
res[i] = 0;
for (int j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways
// to reach s'th stair
static int countWays(int s, int m)
{
return countWaysUtil(s + 1, m);
}
// Driver Code
public static void Main()
{
int s = 4, m = 2;
Console.WriteLine("Number of ways = "
+ countWays(s, m));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A PHP program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
// A recursive function used by countWays
function countWaysUtil($n, $m)
{
$res[0] = 1; $res[1] = 1;
for ($i = 2; $i < $n; $i++)
{
$res[$i] = 0;
for ($j = 1; $j <= $m && $j <= $i; $j++)
$res[$i] += $res[$i - $j];
}
return $res[$n - 1];
}
// Returns number of ways
// to reach s'th stair
function countWays($s, $m)
{
return countWaysUtil($s + 1, $m);
}
// Driver Code
$s = 4;
$m = 2;
echo "Number of ways = ", countWays($s, $m);
// This code is contributed by m_kit
?>
Javascript
<script>
// A Javascript program to count number
// of ways to reach n't stair when
// a person can climb 1, 2, ..m
// stairs at a time
// A recursive function used by countWays
function countWaysUtil(n, m)
{
let res = [];
res[0] = 1;
res[1] = 1;
for (let i = 2; i < n; i++)
{
res[i] = 0;
for (let j = 1; j <= m && j <= i; j++)
res[i] += res[i - j];
}
return res[n - 1];
}
// Returns number of ways
// to reach s'th stair
function countWays(s, m)
{
return countWaysUtil(s + 1, m);
}
// Driver Code
let s = 4;
let m = 2;
document.write("Number of ways = " + countWays(s, m));
// This code is contributed by _saurabh_jaiswal
</script>
Producción
Number of ways = 5
Análisis de Complejidad:
- Complejidad del tiempo: O(m*n)
- Espacio Auxiliar: O(n)
Método 4 : El tercer método utiliza la técnica de la Ventana Deslizante para llegar a la solución.
Enfoque: este método implementa de manera eficiente el enfoque de programación dinámica anterior.
En este enfoque para el i -ésimo escalón, mantenemos una ventana de suma de los últimos m posibles escalones desde la que podemos subir al i -ésimo escalón. En lugar de ejecutar un ciclo interno, mantenemos el resultado del ciclo interno en una variable temporal. Eliminamos los elementos de la ventana anterior y agregamos el elemento de la ventana actual y actualizamos la suma.
El siguiente código implementa la idea anterior.
C++
// A C++ program to count the number of ways
// to reach n'th stair when user
// climb 1 .. m stairs at a time.
// Contributor: rsampaths16
#include <iostream>
using namespace std;
// Returns number of ways
// to reach s'th stair
int countWays(int n, int m)
{
int res[n + 1];
int temp = 0;
res[0] = 1;
for (int i = 1; i <= n; i++)
{
int s = i - m - 1;
int e = i - 1;
if (s >= 0)
{
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
int main()
{
int n = 5, m = 3;
cout << "Number of ways = "
<< countWays(n, m);
return 0;
}
// This code is contributed by shubhamsingh10
C
// A C program to count the number of ways
// to reach n'th stair when user
// climb 1 .. m stairs at a time.
// Contributor: rsampaths16
#include <stdio.h>
// Returns number of ways
// to reach s'th stair
int countWays(int n, int m)
{
int res[n + 1];
int temp = 0;
res[0] = 1;
for (int i = 1; i <= n; i++) {
int s = i - m - 1;
int e = i - 1;
if (s >= 0) {
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
int main()
{
int n = 5, m = 3;
printf("Number of ways = %d",
countWays(n, m));
return 0;
}
Java
// Java program to count number of
// ways to reach n't stair when a
// person can climb 1, 2, ..m
// stairs at a time
class GFG{
// Returns number of ways
// to reach s'th stair
static int countWays(int n, int m)
{
int res[] = new int[n + 1];
int temp = 0;
res[0] = 1;
for(int i = 1; i <= n; i++)
{
int s = i - m - 1;
int e = i - 1;
if (s >= 0)
{
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
public static void main(String[] args)
{
int n = 5, m = 3;
System.out.println("Number of ways = " +
countWays(n, m));
}
}
// This code is contributed by equbalzeeshan
Python3
# Python3 program to count the number
# of ways to reach n'th stair when
# user climb 1 .. m stairs at a time.
# Function to count number of ways
# to reach s'th stair
def countWays(n, m):
temp = 0
res = [1]
for i in range(1, n + 1):
s = i - m - 1
e = i - 1
if (s >= 0):
temp -= res[s]
temp += res[e]
res.append(temp)
return res[n]
# Driver Code
n = 5
m = 3
print('Number of ways =', countWays(n, m))
# This code is contributed by 31ajaydandge
C#
// C# program to count number of
// ways to reach n'th stair when
// a person can climb 1, 2, ..m
// stairs at a time
using System;
class GFG{
// Returns number of ways
// to reach s'th stair
static int countWays(int n, int m)
{
int[] res = new int[n + 1];
int temp = 0;
res[0] = 1;
for(int i = 1; i <= n; i++)
{
int s = i - m - 1;
int e = i - 1;
if (s >= 0)
{
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
public static void Main()
{
int n = 5, m = 3;
Console.WriteLine("Number of ways = " +
countWays(n, m));
}
}
// This code is contributed by equbalzeeshan
Javascript
<script>
// Javascript program to count number of
// ways to reach n't stair when a
// person can climb 1, 2, ..m
// stairs at a time
// Returns number of ways
// to reach s'th stair
function countWays(n , m)
{
var res = Array(n + 1).fill(0);
var temp = 0;
res[0] = 1;
for (i = 1; i <= n; i++) {
var s = i - m - 1;
var e = i - 1;
if (s >= 0) {
temp -= res[s];
}
temp += res[e];
res[i] = temp;
}
return res[n];
}
// Driver Code
var n = 5, m = 3;
document.write("Number of ways = " +
countWays(n, m));
// This code contributed by Rajput-Ji
</script>
Producción
Number of ways = 13
Análisis de Complejidad:
- Complejidad de tiempo: O(n)
- Espacio Auxiliar: O(n)
Este artículo es una contribución de Abhishek . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 5 : El cuarto método usa matemáticas simples, pero esto solo es aplicable para este problema si (el orden no importa) mientras se cuentan los pasos.
Enfoque : en este método simplemente contamos el número de conjuntos que tienen 2.
C++
#include <iostream>
using namespace std;
int main() {
int n;
n=5;
// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
cout<<"Number of ways when order of steps does not matter is : "<<1+(n/2)<<endl;
return 0;
}
Java
import java.util.*;
class GFG{
public static void main(String[] args)
{
int n;
n = 5;
// Here n/2 is done to count the number 2's
// in n 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
System.out.print("Number of ways when order of steps " +
"does not matter is : " + (1 + (n / 2)));
}
}
// This code is contributed by todaysgaurav
Python3
n = 5
# Here n/2 is done to count the number 2's in n
# 1 is added for case where there is no 2.
# eg: if n=4 ans will be 3.
# {1,1,1,1} set having no 2.
# {1,1,2} ans {2,2} (n/2) sets containing 2.
print("Number of ways when order "
"of steps does not matter is : ", 1 + (n // 2))
# This code is contributed by rohitsingh07052
C#
using System;
class GFG{
static public void Main()
{
int n;
n = 5;
// Here n/2 is done to count the number 2's
// in n 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
Console.WriteLine("Number of ways when order of steps " +
"does not matter is : " + (1 + (n / 2)));
}
}
// This code is contributed by Ankita saini
Javascript
<script>
var n;
n = 5;
// Here n/2 is done to count the number 2's in n
// 1 is added for case where there is no 2.
// eg: if n=4 ans will be 3.
// {1,1,1,1} set having no 2.
// {1,1,2} ans {2,2} (n/2) sets containing 2.
document.write("Number of ways when order " +
"of steps does not matter is : ",
parseInt(1 + (n / 2)));
// This code is contributed by Ankita saini
</script>
Producción
Number of ways when order of steps does not matter is : 3
Análisis de Complejidad:
- Complejidad de tiempo : O(1)
- Complejidad espacial : O(1)
Nota: este método solo se aplica a la pregunta Contar caminos a N’th Stair (el orden no importa) .
El orden no importa significa que n = 4 {1 2 1} ,{2 1 1} , {1 1 2} se consideran iguales.
Método 6: Este método utiliza la técnica de Exponenciación Matricial para llegar a la solución.
Aproximación: el número de formas de llegar al n -ésimo escalón (el orden importa) es igual a la suma del número de formas de llegar a (n-1) el escalón y (n-2) el escalón
Esto corresponde a la siguiente relación de recurrencia:
f(n) = f(n-1) + f(n-2) f(1) = 1 f(2) = 2
donde f(n) indica el número de formas de llegar a la escalera n
Nota:
f(1) = 1 porque solo hay 1 forma de llegar a n=1 escalera {1}
f(2) = 2 porque hay 2 formas de llegar a n=2 escaleras {1,1} , {2}
Es un tipo de relación de recurrencia lineal con coeficientes constantes y podemos resolverlos usando el método de exponenciación de arrays que básicamente encuentra una array de transformación para una relación de recurrencia dada y aplica repetidamente esta transformación a un vector base para llegar a la solución).
F(n) = CN-1F(1) where C is the transformation matrix F(1) is the base vector F(n) is the desired solution
Entonces, para nuestro caso la array de transformación C sería:
| 0 | 1 |
| 1 | 1 |
C N-1 se puede calcular utilizando la técnica Divide and Conquer, en O ((K ^ 3) Log n) donde K es la dimensión de C
Y F(1):
| 1 |
| 2 |
Como ejemplo, Para n= 4:
F(4) = C 3 F(1)
do3 = _
| 1 | 2 |
| 2 | 3 |
Por lo tanto, C 3 F(1) =
| 5 |
| 8 |
C++
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LOOP(i, n) for (int i = 1; i < n; i++)
// Computes A*B
// where A,B are square matrices
matrix mul(matrix A, matrix B, long long MOD = 1000000007)
{
int K = A.size();
matrix C(K, vector<long long>(K, 0));
LOOP(i, K)
LOOP(j, K)
LOOP(k, K)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
// Computes A^n
matrix power(matrix A, long long n)
{
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1));
}
else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A);
}
return A;
}
long long ways(int n)
{
vector<long long> F(3);
F[1] = 1;
F[2] = 2;
int K = 2;
long long MOD = 1000000007;
// create K*K matrix
matrix C(K + 1, vector<long long>(K + 1, 0));
/*
A matrix with (i+1)th element as 1 and last row
contains constants
[
[0 1 0 0 ... 0]
[0 0 1 0 ... 0]
[0 0 0 1 ... 0]
[. . . . ... .]
[. . . . ... .]
[c(k) c(k-1) c(k-2) ... c1]
]
*/
for (int i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
C[K][1] = 1;
C[K][2] = 1;
if (n <= 2)
return F[n];
// f(n) = C^(n-1)*F
C = power(C, n - 1);
long long result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
int main()
{
int n = 4;
cout << "Number of ways = " << ways(n) << endl;
}
// This code is contributed by darshang631
Java
import java.util.*;
class GFG
{
// Computes A*B
// where A,B are square matrices
static long[][] mul(long[][] A, long[][] B, long MOD) {
int K = A.length;
long[][] C = new long[K][K];
for (int i = 1; i < K; i++)
for (int j = 1; j < K; j++)
for (int k = 1; k < K; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
// Computes A^n
static long[][] power(long[][] A, long n) {
if (n == 1)
return A;
if (n % 2 != 0)
{
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
}
else
{
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A, 1000000007);
}
return A;
}
static long ways(int n) {
long[] F = new long[3];
F[1] = 1;
F[2] = 2;
int K = 2;
long MOD = 1000000007;
// create K*K matrix
long[][] C = new long[K + 1][K + 1];
/*
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
*/
for (int i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
C[K][1] = 1;
C[K][2] = 1;
if (n <= 2)
return F[n];
// f(n) = C^(n-1)*F
C = power(C, n - 1);
long result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
public static void main(String[] args) {
int n = 4;
System.out.print("Number of ways = " + ways(n) + "\n");
}
}
// This code is contributed by umadevi9616
Python3
# Computes A*B
# where A,B are square matrices
def mul(A, B, MOD):
K = len(A);
C = [[0 for i in range(K)] for j in range(K)] ;
for i in range(1, K):
for j in range(1, K):
for k in range(1, K):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
# Computes A^n
def power( A, n):
if (n == 1):
return A;
if (n % 2 != 0):
# n is odd
# A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
else:
# n is even
# A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n // 2);
A = mul(A, A, 1000000007);
return A;
def ways(n):
F = [0 for i in range(3)];
F[1] = 1;
F[2] = 2;
K = 2;
MOD = 1000000007;
# create K*K matrix
C = [[0 for i in range(K+1)] for j in range(K+1)];
'''
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
'''
for i in range(1,K):
C[i][i + 1] = 1;
# Last row is the constants c(k) c(k-1) ... c1
# f(n) = 1*f(n-1) + 1*f(n-2)
C[K][1] = 1;
C[K][2] = 1;
if (n <= 2):
return F[n];
# f(n) = C^(n-1)*F
C = power(C, n - 1);
result = 0;
# result will be the first row of C^(n-1)*F
for i in range(1,K+1):
result = (result + C[1][i] * F[i]) % MOD;
return result;
# Driver code
if __name__ == '__main__':
n = 4;
print("Number of ways = " , ways(n) , "");
# This code is contributed by gauravrajput1
C#
using System;
public class GFG {
// Computes A*B
// where A,B are square matrices
static long[,] mul(long[,] A, long[,] B, long MOD) {
int K = A.GetLength(0);
long[,] C = new long[K,K];
for (int i = 1; i < K; i++)
for (int j = 1; j < K; j++)
for (int k = 1; k < K; k++)
C[i,j] = (C[i,j] + A[i,k] * B[k,j]) % MOD;
return C;
}
// Computes A^n
static long[,] power(long[,] A, long n) {
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
} else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A, 1000000007);
}
return A;
}
static long ways(int n) {
long[] F = new long[3];
F[1] = 1;
F[2] = 2;
int K = 2;
long MOD = 1000000007;
// create K*K matrix
long[,] C = new long[K + 1,K + 1];
/*
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
*/
for (int i = 1; i < K; ++i) {
C[i,i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
C[K,1] = 1;
C[K,2] = 1;
if (n <= 2)
return F[n];
// f(n) = C^(n-1)*F
C = power(C, n - 1);
long result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1,i] * F[i]) % MOD;
}
return result;
}
public static void Main(String[] args) {
int n = 4;
Console.Write("Number of ways = " + ways(n) + "\n");
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// Computes A*B
// where A,B are square matrices
function mul( A, B , MOD) {
var K = A.length;
var C = Array(K).fill().map(()=>Array(K).fill(0));
for (var i = 1; i < K; i++)
for (var j = 1; j < K; j++)
for (var k = 1; k < K; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
// Computes A^n
function power( A , n) {
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
} else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A, 1000000007);
}
return A;
}
function ways(n) {
var F = Array(3).fill(0);
F[1] = 1;
F[2] = 2;
var K = 2;
var MOD = 1000000007;
// create K*K matrix
var C = Array(K+1).fill().map(()=>Array(K+1).fill(0));
/*
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
*/
for (var i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
C[K][1] = 1;
C[K][2] = 1;
if (n <= 2)
return F[n];
// f(n) = C^(n-1)*F
C = power(C, n - 1);
var result = 0;
// result will be the first row of C^(n-1)*F
for (var i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
var n = 4;
document.write("Number of ways = " + ways(n) + "\n");
// This code is contributed by umadevi9616
</script>
Producción
Number of ways = 5
Análisis de Complejidad:
- Complejidad de tiempo: O (Log n)
- Complejidad espacial: O(1)
Generalización del Problema:
Dada una array A {a1, a2, …., am} que contiene todos los escalones válidos, calcule el número de formas de llegar al enésimo escalón. (El orden sí importa)
Ejemplos :
Input:
A = [1,2]
n = 4
Output: 5
Explanation:
This is the given problem, i.e, count the number of ways to reach n=4 stairs with climbing 1 or 2 stairs at a time
Therefore, ways will be: {1,1,1,1} {1,1,2} {1,2,1} {2,1,1} {2,2} = 5
Input:
A = [2,4,5]
n = 9
Output: 5
Explanation:
There are 5 ways to reach n=9 stairs with climbing 2 or 4 or 5 stairs at a time
Therefore, ways will be: {5,4} {4,5} {2,2,5} {2,5,2} {5,2,2} = 5
Acercarse:
El número de formas de llegar al n-ésimo escalón viene dado por la siguiente relación de recurrencia
Sea K el elemento más grande de A.
Paso 1: Calcule el vector base F(1) (que consta de f(1) …. f(K) )
Se puede hacer en tiempo O(m 2 K) utilizando el enfoque de programación dinámica de la siguiente manera:
Tomemos A = {2,4,5} como ejemplo. Para calcular F(1) = { f(1), f(2), f(3), f(4), f(5) } mantendremos una array inicialmente vacía y le agregaremos iterativamente A i y para cada A i encontraremos el número de caminos para llegar a [A i-1 , a A i, ]
Por lo tanto para A = {2 ,4 ,5}
Sea T la array inicialmente vacía
Iteration 1: T = {2} n = {1,2} dp = {0,1} (Number of ways to reach n=1,2 with steps given by T)
Iteration 2: T = {2,4} n = {1,2,3,4} dp = {0,1,0,2} (Number of ways to reach n=1,2,3,4 with steps given by T)
Iteration 3: T = {2,4,5} n = {1,2,3,4,5} dp = {0,1,0,2,1} (Number of ways to reach n=1,2,3,4,5 with steps given by T)
Nota : dado que algunos valores ya están calculados (1,2 para la iteración 2, etc.), podemos evitarlos en el ciclo
Después de todas las iteraciones, la array dp sería: [0,1,0,2,1]
Así, el vector base F(1) para A = [2,4,5] es:
| 0 |
| 1 |
| 0 |
| 2 |
| 1 |
Ahora que tenemos el vector base F(1), el cálculo de C (array de transformación) es fácil
Paso 2: Calcular C, la array de transformación
Es una array que tiene elementos A i,i+1 = 1 y la última fila contiene constantes
Ahora las constantes se pueden determinar por la presencia de ese elemento en A
Entonces para A = [2,4,5] las constantes serán c = [1,1,0,1,0] (C i = 1 si (K-i+1) está presente en A, o bien 0 donde 1 <= yo <= k)
Por lo tanto, la array de transformación C para A =[2,4,5] es:
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 |
Paso 3: Calcular F(n)
Para calcular F(n), se utiliza la siguiente fórmula:
F(n) = Cn-1F(1)
Ahora que tenemos C y F (1), podemos usar la técnica Divide and Conquer para encontrar C n-1 y, por lo tanto, la salida deseada.
C++
#include <bits/stdc++.h>
using namespace std;
typedef vector<vector<long long> > matrix;
#define LOOP(i, n) for (int i = 1; i < n; i++)
// Computes A*B when A,B are square matrices of equal
// dimensions)
matrix mul(matrix A, matrix B, long long MOD = 1000000007)
{
int K = A.size();
matrix C(K, vector<long long>(K, 0));
LOOP(i, K)
LOOP(j, K)
LOOP(k, K)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
matrix power(matrix A, long long n)
{
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1));
}
else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A);
}
return A;
}
vector<long long> initialize(vector<long long> A)
{
// Initializes the base vector F(1)
int K = A[A.size() - 1]; // Assuming A is sorted
vector<long long> F(K + 1, 0);
vector<long long> dp(K + 1);
dp[0] = 0;
dp[A[1]] = 1; // There is one and only one way to reach
// first element
F[A[1]] = 1;
for (int i = 2; i < A.size(); ++i) {
// Loop through A[i-1] to A[i] and fill the dp array
for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
// dp[j] = dp[j-A[0]] + .. + dp[j-A[i-1]]
for (int k = 1; k < i; ++k) {
dp[j] += dp[j - A[k]];
}
}
// There will be one more way to reach A[i]
dp[A[i]] += 1;
F[A[i]] = dp[A[i]];
}
return F;
}
long long ways(vector<long long> A, int n)
{
int K = A[A.size() - 1]; // Assuming A is sorted
vector<long long> F = initialize(A); // O(m^2*K)
int MOD = 1000000007;
// create K*K matrix
matrix C(K + 1, vector<long long>(K + 1, 0));
/*
A matrix with (i+1)th element as 1 and last row contains
constants
[
[0 1 0 0 ... 0]
[0 0 1 0 ... 0]
[0 0 0 1 ... 0]
[. . . . ... .]
[. . . . ... .]
[c(k) c(k-1) c(k-2) ... c1]
]
*/
for (int i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
for (int i = 1; i < A.size(); ++i) {
C[K][K - A[i] + 1] = 1;
}
if (n <= K)
return F[n];
// F(n) = C^(n-1)*F
C = power(C, n - 1); // O(k^3Log(n))
long long result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
int main()
{
int n = 9;
vector<long long> A = {
0, 2, 4, 5
}; // 0 is just because we are using 1 based indexing
cout << "Number of ways = " << ways(A, n) << endl;
}
// This code is contributed by darshang631
Java
import java.util.*;
class GFG{
// Computes A*B when A,B are square matrices of equal
// dimensions)
static int[][] mul(int[][] A, int[][] B,int MOD)
{
int K = A.length;
int[][] C = new int[K][K];
for (int i = 1; i < K; i++)
for (int j = 1; j < K; j++)
for (int k = 1; k < K; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
static int[][] power(int[][] A, long n)
{
if (n == 1)
return A;
if (n % 2 != 0)
{
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
}
else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A, 1000000007);
}
return A;
}
static int[] initialize(int[] A)
{
// Initializes the base vector F(1)
int K = A[A.length - 1]; // Assuming A is sorted
int[] F = new int[K+1];
int[] dp = new int[K+1];
dp[0] = 0;
dp[A[1]] = 1; // There is one and only one way to reach
// first element
F[A[1]] = 1;
for (int i = 2; i < A.length; ++i)
{
// Loop through A[i-1] to A[i] and fill the dp array
for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
// dp[j] = dp[j-A[0]] + .. + dp[j-A[i-1]]
for (int k = 1; k < i; ++k) {
dp[j] += dp[j - A[k]];
}
}
// There will be one more way to reach A[i]
dp[A[i]] += 1;
F[A[i]] = dp[A[i]];
}
return F;
}
static int ways(int[] A, int n)
{
int K = A[A.length - 1]; // Assuming A is sorted
int[] F = initialize(A); // O(m^2*K)
int MOD = 1000000007;
// create K*K matrix
int[][] C = new int[K + 1][K + 1];
/*
A matrix with (i+1)th element as 1 and last row contains
constants
[
[0 1 0 0 ... 0]
[0 0 1 0 ... 0]
[0 0 0 1 ... 0]
[. . . . ... .]
[. . . . ... .]
[c(k) c(k-1) c(k-2) ... c1]
]
*/
for (int i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
for (int i = 1; i < A.length; ++i) {
C[K][K - A[i] + 1] = 1;
}
if (n <= K)
return F[n];
// F(n) = C^(n-1)*F
C = power(C, n - 1); // O(k^3Log(n))
int result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
public static void main(String[] args)
{
int n = 9;
int[] A = {0, 2, 4, 5};
// 0 is just because we are using 1 based indexing
System.out.print("Number of ways = " + ways(A, n) +"\n");
}
}
// This code is contributed by umadevi9616
Python3
# Computes A*B when A,B are square matrices of equal
# dimensions)
def mul(A, B, MOD):
K = len(A);
C = [[0 for i in range(K)] for j in range(K)] ;
for i in range(1, K):
for j in range(1, K):
for k in range(1, K):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
def power(A, n):
if (n == 1):
return A;
if (n % 2 != 0):
# n is odd
# A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
else:
# n is even
# A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n // 2);
A = mul(A, A, 1000000007);
return A;
def initialize(A):
# Initializes the base vector F(1)
K = A[len(A)-1]; # Assuming A is sorted
F = [0 for i in range(K+1)];
dp = [0 for i in range(K+1)];
dp[0] = 0;
dp[A[1]] = 1; # There is one and only one way to reach
# first element
F[A[1]] = 1;
for i in range(2,len(A)):
# Loop through A[i-1] to A[i] and fill the dp array
for j in range(A[i - 1] + 1,A[i]+1):
# dp[j] = dp[j-A[0]] + .. + dp[j-A[i-1]]
for k in range(1,i):
dp[j] += dp[j - A[k]];
# There will be one more way to reach A[i]
dp[A[i]] += 1;
F[A[i]] = dp[A[i]];
return F;
def ways(A, n):
K = A[len(A) - 1]; # Assuming A is sorted
F = initialize(A); # O(m^2*K)
MOD = 1000000007;
# create K*K matrix
C = [[0 for i in range(K+1)] for j in range(K+1)];
'''
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
'''
for i in range(1,K):
C[i][i + 1] = 1;
# Last row is the constants c(k) c(k-1) ... c1
# f(n) = 1*f(n-1) + 1*f(n-2)
for i in range(1, len(A)):
C[K][K - A[i] + 1] = 1;
if (n <= K):
return F[n];
# F(n) = C^(n-1)*F
C = power(C, n - 1); # O(k^3Log(n))
result = 0;
# result will be the first row of C^(n-1)*F
for i in range(1, K+1):
result = (result + C[1][i] * F[i]) % MOD;
return result;
# Driver code
if __name__ == '__main__':
n = 9;
A = [ 0, 2, 4, 5] ;
# 0 is just because we are using 1 based indexing
print("Number of ways = " ,ways(A, n));
# This code is contributed by gauravrajput1
C#
using System;
public class GFG {
// Computes A*B when A,B are square matrices of equal
// dimensions)
static int[,] mul(int[,] A, int[,] B, int MOD) {
int K = A.GetLength(0);
int[,] C = new int[K,K];
for (int i = 1; i < K; i++)
for (int j = 1; j < K; j++)
for (int k = 1; k < K; k++)
C[i,j] = (C[i,j] + A[i,k] * B[k,j]) % MOD;
return C;
}
static int[,] power(int[,] A, long n) {
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
} else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, n / 2);
A = mul(A, A, 1000000007);
}
return A;
}
static int[] initialize(int[] A) {
// Initializes the base vector F(1)
int K = A[A.Length - 1]; // Assuming A is sorted
int[] F = new int[K + 1];
int[] dp = new int[K + 1];
dp[0] = 0;
dp[A[1]] = 1; // There is one and only one way to reach
// first element
F[A[1]] = 1;
for (int i = 2; i < A.Length; ++i) {
// Loop through A[i-1] to A[i] and fill the dp array
for (int j = A[i - 1] + 1; j <= A[i]; ++j) {
// dp[j] = dp[j-A[0]] + .. + dp[j-A[i-1]]
for (int k = 1; k < i; ++k) {
dp[j] += dp[j - A[k]];
}
}
// There will be one more way to reach A[i]
dp[A[i]] += 1;
F[A[i]] = dp[A[i]];
}
return F;
}
static int ways(int[] A, int n) {
int K = A[A.Length - 1]; // Assuming A is sorted
int[] F = initialize(A); // O(m^2*K)
int MOD = 1000000007;
// create K*K matrix
int[,] C = new int[K + 1,K + 1];
/*
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
*/
for (int i = 1; i < K; ++i) {
C[i,i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
for (int i = 1; i < A.GetLength(0); ++i) {
C[K,K - A[i] + 1] = 1;
}
if (n <= K)
return F[n];
// F(n) = C^(n-1)*F
C = power(C, n - 1); // O(k^3Log(n))
int result = 0;
// result will be the first row of C^(n-1)*F
for (int i = 1; i <= K; ++i) {
result = (result + C[1,i] * F[i]) % MOD;
}
return result;
}
public static void Main(String[] args) {
int n = 9;
int[] A = { 0, 2, 4, 5 };
// 0 is just because we are using 1 based indexing
Console.Write("Number of ways = " + ways(A, n) + "\n");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Computes A*B when A,B are square matrices of equal
// dimensions)
function mul(A, B , MOD) {
var K = A.length;
var C = Array(K).fill().map(()=>Array(K).fill(0));
for (var i = 1; i < K; i++)
for (var j = 1; j < K; j++)
for (var k = 1; k < K; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
function power(A , n) {
if (n == 1)
return A;
if (n % 2 != 0) {
// n is odd
// A^n = A * [ A^(n-1) ]
A = mul(A, power(A, n - 1), 1000000007);
} else {
// n is even
// A^n = [ A^(n/2) ] * [ A^(n/2) ]
A = power(A, parseInt(n / 2));
A = mul(A, A, 1000000007);
}
return A;
}
function initialize(A) {
// Initializes the base vector F(1)
var K = A[A.length - 1]; // Assuming A is sorted
var F = Array(K+1).fill(0);
var dp = Array(K+1).fill(0);
dp[0] = 0;
dp[A[1]] = 1; // There is one and only one way to reach
// first element
F[A[1]] = 1;
for (var i = 2; i < A.length; ++i) {
// Loop through A[i-1] to A[i] and fill the dp array
for (var j = A[i - 1] + 1; j <= A[i]; ++j) {
// dp[j] = dp[j-A[0]] + .. + dp[j-A[i-1]]
for (var k = 1; k < i; ++k) {
dp[j] += dp[j - A[k]];
}
}
// There will be one more way to reach A[i]
dp[A[i]] += 1;
F[A[i]] = dp[A[i]];
}
return F;
}
function ways(A , n) {
var K = A[A.length - 1]; // Assuming A is sorted
var F = initialize(A); // O(m^2*K)
var MOD = 1000000007;
// create K*K matrix
var C = Array(K+1).fill().map(()=>Array(K+1).fill(0));
/*
* A matrix with (i+1)th element as 1 and last row contains constants [ [0 1 0 0
* ... 0] [0 0 1 0 ... 0] [0 0 0 1 ... 0] [. . . . ... .] [. . . . ... .] [c(k)
* c(k-1) c(k-2) ... c1] ]
*/
for (var i = 1; i < K; ++i) {
C[i][i + 1] = 1;
}
// Last row is the constants c(k) c(k-1) ... c1
// f(n) = 1*f(n-1) + 1*f(n-2)
for (var i = 1; i < A.length; ++i) {
C[K][K - A[i] + 1] = 1;
}
if (n <= K)
return F[n];
// F(n) = C^(n-1)*F
C = power(C, n - 1); // O(k^3Log(n))
var result = 0;
// result will be the first row of C^(n-1)*F
for (var i = 1; i <= K; ++i) {
result = (result + C[1][i] * F[i]) % MOD;
}
return result;
}
var n = 9;
var A = [ 0, 2, 4, 5 ];
// 0 is just because we are using 1 based indexing
document.write("Number of ways = " + ways(A, n) + "\n");
// This code is contributed by gauravrajput1
</script>
Producción
Number of ways = 5
Análisis de Complejidad:
Time Complexity: O( m2K + K3Logn )
where
m is the size of Array A
K is the largest element in A
n denotes the stair number (nth stair)
Space Complexity: O(K2)
Nota:
Este enfoque es ideal cuando n es demasiado grande para la iteración.
Por ejemplo: Considere este enfoque cuando (1 ≤ n ≤ 10 9 ) y (1 ≤ m,k ≤ 10 2 )
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