Advertisement
bbescos

Untitled

Feb 18th, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <iostream>
  10.  
  11. using namespace std;
  12.  
  13. // You are climbing a stair case. It takes n steps to reach to the top.
  14. // Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
  15. /*
  16. int climbStairs(int n) {
  17.    
  18.     if (n < 3)
  19.         return n;
  20.    
  21.     int two_ago = 1; // number of ways to reach n = 1
  22.     int one_ago = 2; // number of ways to reach n = 2
  23.     int current;
  24.    
  25.     for (int i = 3; i <= n; ++i) {
  26.         current = two_ago + one_ago;
  27.         two_ago = one_ago;
  28.         one_ago = current;
  29.     }
  30.    
  31.     return current;
  32. }
  33. */
  34.  
  35. // You are climbing a stair case. It takes n steps to reach to the top.
  36. // Each time you can either climb 1, 2 or 3 steps. In how many distinct ways can you climb to the top?
  37.  
  38. int climbStairs(int n) {
  39.    
  40.     if (n < 3)
  41.         return n;
  42.     if (n == 3)
  43.         return 4;
  44.    
  45.     int three_ago = 1; // number of ways to reach n = 1
  46.     int two_ago = 2; // number of ways to reach n = 2
  47.     int one_ago = 4; // number of ways to reach n = 3
  48.     int current;
  49.    
  50.     for (int i = 4; i <= n; ++i) {
  51.         current = three_ago + two_ago + one_ago;
  52.         three_ago = two_ago;
  53.         two_ago = one_ago;
  54.         one_ago = current;
  55.     }
  56.    
  57.     return current;
  58. }
  59.  
  60. int main()
  61. {
  62.     int n = 6;
  63.     std::cout << climbStairs(n) << std::endl;
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement