爬n级楼梯，允许从1跳到n（三种不同的方法）-yiteyi-C++库

一只猴子站在下面有N级台阶的楼梯旁。考虑到它一次可以跨越1到N步，计算一下它可以通过多少种方式到达楼梯顶部？

null

例如：

Input : 2Output : 2It can either take (1, 1) or (2) toreach the top. So, total 2 waysInput : 3Output : 4Possibilities : (1, 1, 1), (1, 2), (2, 1),(3). So, total 4 ways

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

有三种不同的方式来思考这个问题。

在所有可能的解决方案中，一个步骤要么被猴子踩到，要么可以跳过。所以使用基本计数原理，第一步有两种参与方式，第二步也有两种参与方式，依此类推。但最后一步总是要踩上去。

  2 x 2 x 2 x .... x 2(N-1 th step) x 1(Nth step)   = 2^(N-1) different ways.

让我们为用例定义一个函数F（n）。F（n）表示从底部到达顶部的所有可能方式，楼梯有n个台阶，其中最小跳跃为1个台阶，最大跳跃为n个台阶。现在，对于猴子来说，它可以用N种不同的方式（1步、2步、3步..N步）做出第一步。如果第一步是一步，那么它还有N-1步需要征服，这可以通过F（N-1）的方式实现。如果第一步是两步，那么它将有N-2步要完成，这可以通过F（N-2）的方式实现。综合起来，

F(N) = F(N-1) + F(N-2) + F(N-3) + ... +                       F(2) + F(1) + F(0) Now, F(0) = 1F(1) = 1F(2) = 2F(3) = 4Hence,F(N) = 1 + 1 + 2 + 4 + ... + F(n-1)     = 1 + 2^0 + 2^1 + 2^2 + ... + 2^(n-2)     = 1 + [2^(n-1) - 1]

C++

                         // C++ program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
                         #include <iostream>                       
           
                         int                                     calculateLeaps(                                     int                                     n)                       
                         {                       
                                                 if                                     (n == 0 || n == 1) {                       
                                                 return                                     1;                       
                                                 }                       
                                                 else                                     {                       
                                                 int                                     leaps = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 leaps += calculateLeaps(i);                       
                                                 return                                     leaps;                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     calculateLeaps(                                     int                                     );                       
                                                 std::cout << calculateLeaps(4) << std::endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
                         class                                     GFG {                       
                                                 static                                     int                                     calculateLeaps(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n ==                                     0                                     || n ==                                     1                                     ) {                       
                                                 return                                     1                                     ;                       
                                                 }                       
                                                 else                                     {                       
                                                 int                                     leaps =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 leaps += calculateLeaps(i);                       
                                                 return                                     leaps;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 System.out.println(calculateLeaps(                                     4                                     ));                       
                                                 }                       
                         }                       
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program to count                       
                         # total number of ways                       
                         # to reach n-th stair with                       
                         # all jumps allowed                       
           
                         def                                     calculateLeaps(n):                       
                                                 if                                     n                                     =                                     =                                     0                                     or                                     n                                     =                                     =                                     1                                     :                       
                                                 return                                     1                                     ;                       
                                                 else                                     :                       
                                                 leaps                                     =                                     0                                     ;                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,n):                       
                                                 leaps                                     =                                     leaps                                     +                                     calculateLeaps(i);                       
                                                 return                                     leaps;                       
           
                         # Driver code                       
                         print                                     (calculateLeaps(                                     4                                     ));                       
           
                         # This code is contributed by mits                       

C#

                         // C# program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Function to calculate leaps                       
                                                 static                                     int                                     calculateLeaps(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 0 || n == 1) {                       
                                                 return                                     1;                       
                                                 }                       
                                                 else                                     {                       
                                                 int                                     leaps = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 leaps += calculateLeaps(i);                       
                                                 return                                     leaps;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 Console.WriteLine(calculateLeaps(4));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to count total                       
                         // number of ways to reach                       
                         // n-th stair with all                       
                         // jumps allowed                       
           
                         // function return the                       
                         // number of ways                       
                         function                                     calculateLeaps(                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     == 0 ||                                     $n                                     == 1)                       
                                                 {                       
                                                 return                                     1;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 $leaps                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $leaps                                     += calculateLeaps(                                     $i                                     );                       
                                                 return                                     $leaps                                     ;                       
                                                 }                       
                         }                       
           
                                                 // Driver Code                       
                                                 echo                                     calculateLeaps(4),                                     ""                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to count total number of ways                       
                                                 // to reach n-th stair with all jumps allowed                       
                                   
                                                 // Function to calculate leaps                       
                                                 function                                     calculateLeaps(n)                       
                                                 {                       
                                                 if                                     (n == 0 || n == 1) {                       
                                                 return                                     1;                       
                                                 }                       
                                                 else                                     {                       
                                                 let leaps = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 leaps += calculateLeaps(i);                       
                                                 return                                     leaps;                       
                                                 }                       
                                                 }                       
                                   
                                                 document.write(calculateLeaps(4));                       
                                   
                         </script>                       

输出：

2.可以使用动态规划（自下而上方法）改进上述解决方案

                              Leaps(3)                         3/      2|         1                     Leaps(0)   Leaps(1)            Leaps(2)                    /   |                      3/       2|     1          Leaps(-3) Leaps(-2)  Leaps(-1)   Lepas(-1) Leaps(0) Leaps(1)

C++

                         // C++ program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
           
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         int                                     calculateLeaps(                                     int                                     n,                                     int                                     dp[]){                       
                                                 if                                     (n == 0){                       
                                                 return                                     1 ;                       
                                                 }                                     else                                     if                                     (n < 0){                       
                                                 return                                     0 ;                       
                                                 }                       
                                   
                                                 if                                     (dp[n] != 0 ){                       
                                                 return                                     dp[n] ;                       
                                                 }                       
           
                                                 int                                     count = 0;                       
                                                 for                                     (                                     int                                     i = 0 ; i < n ; i++ ){                       
                                                 count += calculateLeaps(i, dp)  ;                       
                                                 }                       
                                   
                                                 dp[n] = count ;                       
                                                 return                                     count ;                       
                                   
                         }                       
                         int                                     main() {                       
                                                 int                                     n = 4 ;                       
                                   
                                                 int                                     dp[n+1] = {0} ;                       
                                   
                                                 cout<<calculateLeaps(n,dp) ;                       
           
                                                 return                                     0;                       
                                   
                         }                       

3.让我们把这个问题分解成几个小的子问题。猴子必须走最后一步，前N-1步是可选的。猴子在到达顶端之前可以跨上0步，这是跳到顶端的最大一步。或者，它可以决定在中间只踩一次，这可以通过n-1种方式实现[ ^（N-1） C _1. ].如此类推，它只能跨上两级台阶才能到达顶部 ^（N-1） C _2. 方式。把…放在一起。。 F（N）= ^（N-1） C ₀ + ^（N-1） C _1. + ^（N-1） C _2. + … + ^（N-1） C _（N-2） + ^（N-1） C _（N-1）这是二项式系数的和。 =2^（n-1）

C++

                         // C++ program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                                                 int                                     calculateLeaps(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 0)                       
                                                 return                                     1;                       
                                                 return                                     (1 << (n - 1));                       
                                                 }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     calculateLeaps(                                     int                                     );                       
                                                 std::cout << calculateLeaps(4) << std::endl;                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by shivanisinghss2110.                       

JAVA

                         // Java program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
                         class                                     GFG {                       
                                                 static                                     int                                     calculateLeaps(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n ==                                     0                                     )                       
                                                 return                                     1                                     ;                       
                                                 return                                     (                                     1                                     << (n -                                     1                                     ));                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 System.out.println(calculateLeaps(                                     4                                     ));                       
                                                 }                       
                         }                       
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # python3 program to count                       
                         # total number of ways                       
                         # to reach n-th stair with                       
                         # all jumps allowed                       
           
                         def                                     calculateLeaps(n):                       
                                                 if                                     (n                                     =                                     =                                     0                                     ):                       
                                                 return                                     1                                     ;                       
                                                 return                                     (                                     1                                     << (n                                     -                                     1                                     ));                       
           
                         # Driver code                       
                         print                                     (calculateLeaps(                                     4                                     ));                       
           
                         # This code is contributed                       
                         # by mits                       

C#

                         // C# program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Function to calculate leaps                       
                                                 static                                     int                                     calculateLeaps(                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 0)                       
                                                 return                                     1;                       
                                                 return                                     (1 << (n - 1));                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 Console.WriteLine(calculateLeaps(4));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to count total                       
                         // number of ways to reach n-th                       
                         // stair with all jumps allowed                       
           
                         // Function to calculate leaps                       
                         function                                     calculateLeaps(                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     == 0)                       
                                                 return                                     1;                       
                                                 return                                     (1 << (                                     $n                                     - 1));                       
                         }                       
           
                         // Driver code                       
                         echo                                     calculateLeaps(4);                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // javascript program to count total number of ways                       
                         // to reach n-th stair with all jumps allowed                       
           
                         function                                     calculateLeaps(n)                       
                         {                       
                                                 if                                     (n == 0)                       
                                                 return                                     1;                       
                                                 return                                     (1 << (n - 1));                       
                         }                       
           
                         // Driver code                       
                         document.write(calculateLeaps(4));                       
           
                         // This code is contributed by Amit Katiyar                       
                         </script>                       

输出：

本文由 帕塔·普拉蒂姆·马利克 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章