[leetcode] 계단을 오르는 귀속과 비귀속 방법
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?
[분석]
매거를 이용하여 일반 표현식을 추상화하다
n=0 시, f(n)=1
n=1,f(n)=1
n=2,f(n)=2
n=3,fn=3
n=4,fn=5
f(2)=f(1)+f(0)
f(3)=f(2)+f(1)
f(4)=f(3)+f(2)
.......
f(n)=f(n-2)+f(n-1)
위의 분석을 통해 일반적인 표현식을 요약할 수 있습니다.
귀속 알고리즘을 쉽게 작성할 수 있습니다.
class Solution {
public:
int climbStairs(int n) {
//f(n)=f(n-2)+f(n-1)
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
};그러나 위의 방법은 한 가지 단점이 있다. 그것은 중복 계산이 많아서 시간이 오래 걸린다는 것이다. 아래의 알고리즘은 중간 결과를 저장했다. 만약에 이미 계산을 했다면 중간 결과 값을 직접 되돌려주고 없으면 귀속 계산을 해서 결과를 저장한다.
실현 방법
class Solution {
public:
int climbStairs(int n) {
//f(n)=f(n-2)+f(n-1)
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (res.size() >= (n-2)) {
return res.at(n - 3);
}
res.push_back(climbStairs(n - 1) + climbStairs(n - 2));
return res.back();
//return climbStairs(n - 1) + climbStairs(n - 2);
}
private:
vector<int> res;
};실현 방법 2 중복 계산을 피하지만 결국은 귀속을 통해 실현된다. 만약에 비귀속의 방법을 통해 실현된다면?위의 분석을 통해 알 수 있듯이 사실 교환 가치 방식은 다음 값을 교체할 수 있기 때문에 비귀속의 실현 방법은 다음과 같다.
class Solution {
public:
int climbStairs(int n) {
//f(n)=f(n-2)+f(n-1)
if (n <= 1) {
return 1;
}
int nCur,nPrev,nPrevP;
nPrevP = 1;
nPrev = 1;
for (int i = 2; i <= n; ++i) {
nCur = nPrev + nPrevP;
nPrevP = nPrev;
nPrev = nCur;
}
return nCur;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
