【LeetCode】70. Climbing Stairs

Problem here

Problem

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?

Solution

這題之前做過 
就是超級樓梯那條
class Solution {
public:
    int climbStairs(int n) {
        vector<int> f;
        f.push_back(1);
        f.push_back(1);
        for(int i = 2; i <= n; i++){
            f.push_back(f[i-1] + f[i-2]);
        }
        return f[n];

    }
};

Comments

Post a Comment

Popular posts from this blog

【CodeForces】A. Lucky Division

Problem  here Problem Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits  4  and  7 . For example, numbers  47 ,  744 ,  4  are lucky and  5 , 17 ,  467  are not. Petya calls a number  almost lucky  if it could be evenly divided by some lucky number. Help him find out if the given number  n  is almost lucky. Input The single line contains an integer  n   (1 ≤  n  ≤ 1000)  — the number that needs to be checked. Output In the only line print “ YES " (without the quotes), if number  n  is almost lucky. Otherwise, print “ NO " (without the quotes). Sample test(s) input 47 output YES input 16 output YES input 78 output NO Note Note that all lucky numbers are almost lucky as any number is evenly divisible by itself. In the first sample...
Read more

【UVa】10298 - Power Strings

Problem  here Given two strings a and b we define a ∗ b to be their concatenation. For  example, if a = ‘abc’ and b = ‘def’ then a ∗ b = ‘abcdef’. If we think of  concatenation as multiplication, exponentiation by a non-negative integer  is defined in the normal way: a  0 = ‘’ (the empty string) and a  (n+1) =  a ∗ (a  n). Input Each test case is a line of input representing s, a string of printable characters.  The length of s will be at least 1 and will not exceed 1 million  characters. A line containing a period follows the last test case. Output For each s you should print the largest n such that s = a  n for some string  a. Sample Input abcd  aaaa  ababab  . Sample Output 1  4  3 Solution #include <iostream> #include <string> //#include <fstream> #define MAX_NUM 9999999 using namespace std ; //ifstream fin("10298.in"); //ofstream fout("10298.out"); ...
Read more

【CodeForces】A. Helpful Maths

Problem  here Problem Xenia the beginner mathematician is a third year student at elementary school. She is now learning the addition operation. The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. To make the calculation easier, the sum only contains numbers 1, 2 and 3. Still, that isn’t enough for Xenia. She is only beginning to count, so she can calculate a sum only if the summands follow in non-decreasing order. For example, she can’t calculate sum 1+3+2+1 but she can calculate sums 1+1+2 and 3+3. You’ve got the sum that was written on the board. Rearrange the summans and print the sum in such a way that Xenia can calculate the sum. Input The first line contains a non-empty string  s  — the sum Xenia needs to count. String  s  contains no spaces. It only contains digits and characters “ + “. Besides, string  s  is a correct sum of numbers 1, 2 and 3. String  s  is at most 100 char...
Read more