LetCode 브러시 문제: Climbing Stairs - Fibonacci 수열과 유사
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
이 문제는 피바나시 수열과 유사하다.
해법은 두 가지가 있는데 하나는 귀속이고 하나는 시비귀속이다.
비반복:
class Solution {
public:
int climbStairs(int n) {
if(n<=2)
return n;
int n1 = 1;
int n2 = 2;
int temp =3;
int t;
while(temp<=n)
{
t = n1 + n2;
n1 = n2;
n2 = t;
temp++;
}
return n2;
}
};반복:
귀속 효율이 비교적 낮다. 나의 귀속 알고리즘은LetCode시스템에 받아들여지지 않았다. 이유는 n이 매우 크면 귀속이 너무 많다는 것이다.
개선된 방법은 모든 연산의 결과를 기록하는 것이다. 그러면 다음에 계산할 때 이미 값을 계산했다면 다시 한 번 계산할 필요가 없다.
향상된 알고리즘:
class Solution {
unordered_map<int, int> res = {{1,1},{2,2},{3,3}}; // climbStairs ，
public:
int climbStairs(int n) {
if(res.find(n) == res.end())
{
res[n] = climbStairs(n-1) + climbStairs(n-2);
}
return res[n];
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
