online advertising

Friday, April 10, 2015

LeetCode OJ - Climbing Stairs

Problem:

Please find the problem here.

Solution:

Another classic problem in dynamic programming. The problem manifest itself in many different flavors. Counting the number of paths, counting the number of ways to reach top, counting the number of ways of change coin, ... etc.

The key idea is that to to reach n steps is to either make a step of 1 and count the number of steps to reach the top, or make a step of 2 and count the number of steps to reach the top.

So the recurrence is $ T(n) = T(n - 1) + T(n - 2) $, and therefore the solution is obvious! Fibonacci numbers!

I am aware of the logarithmic solution for Fibonacci numbers. But notice the required return type is int, so there is no need, the recursive formulation introduce more overhead than speed.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/climbing-stairs/

#include "LEET_CLIMBING_STAIRS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_CLIMBING_STAIRS
{
    class Solution
    {
    public:
        int climbStairs(int n)
        {
            if (n == 0 || n == 1)
            {
                return 1;
            }
            else
            {
                int a = 1;
                int b = 1;
                int c = 0;
                for (int i = 2; i <= n; i++)
                {
                    c = a + b;
                    a = b;
                    b = c;
                }
                return c;
            }
        }
    };
};

using namespace _LEET_CLIMBING_STAIRS;

int LEET_CLIMBING_STAIRS()
{
    Solution solution;
    for (int i = 1; i <= 10; i++)
    {
        cout << solution.climbStairs(i) << endl;
    }
    return 0;
}

No comments :

Post a Comment