Leetcode climbing-stair

3342 단어 LeetCode
이 문제는 어렵지 않다. 먼저 귀속 방법을 쓴다. n층 계단을 올라가는 것은 두 가지 상황이 있다. 하나, 한 걸음 올라가면 2, 두 걸음 올라가면 클라이맥스테이어(n)=클라이맥스테이어(n-1)+클라이맥스테이어(n-1)를 얻을 수 있다.귀속 방법에 따라 순환하는 방법을 쓰면 된다
/**********************************************************************************
* * 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?
* * **********************************************************************************/

#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;
int climbStairs(int n) {
 if (n <= 3) return n;
 int a[2] = { 2,3 };
 for (int i = 4; i <= n; i++) {
 int t = a[0] + a[1];
 a[0] = a[1];
 a[1] = t;
 }
 return a[1];
}
//Time too long
int climbStairs2(int n) {
 if (n <= 3) return n;
 return climbStairs2(n - 1) + climbStairs2(n - 2);
}
// , ,
int main()
{
 clock_t start_time = clock();
 cout << climbStairs(40) << endl;
 clock_t end_time = clock();
 cout << "Running time :" << (end_time - start_time) << "ms" << endl;
 clock_t start_time1 = clock();
 cout << climbStairs2(40) << endl;
 clock_t end_time1= clock();
 cout << "Running time :" << (end_time1 - start_time1)<< "ms" << endl;
}

좋은 웹페이지 즐겨찾기