Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /******************************************************************************
- Online C++ Compiler.
- Code, Compile, Run and Debug C++ program online.
- Write your code in this editor and press "Run" button to compile and execute it.
- *******************************************************************************/
- #include <iostream>
- using namespace std;
- // You are climbing a stair case. It takes n steps to reach to the top.
- // Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
- /*
- int climbStairs(int n) {
- if (n < 3)
- return n;
- int two_ago = 1; // number of ways to reach n = 1
- int one_ago = 2; // number of ways to reach n = 2
- int current;
- for (int i = 3; i <= n; ++i) {
- current = two_ago + one_ago;
- two_ago = one_ago;
- one_ago = current;
- }
- return current;
- }
- */
- // You are climbing a stair case. It takes n steps to reach to the top.
- // Each time you can either climb 1, 2 or 3 steps. In how many distinct ways can you climb to the top?
- int climbStairs(int n) {
- if (n < 3)
- return n;
- if (n == 3)
- return 4;
- int three_ago = 1; // number of ways to reach n = 1
- int two_ago = 2; // number of ways to reach n = 2
- int one_ago = 4; // number of ways to reach n = 3
- int current;
- for (int i = 4; i <= n; ++i) {
- current = three_ago + two_ago + one_ago;
- three_ago = two_ago;
- two_ago = one_ago;
- one_ago = current;
- }
- return current;
- }
- int main()
- {
- int n = 6;
- std::cout << climbStairs(n) << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement