20.Climbing Stairs
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
분석: f(n)=f(n-1)+f(n-2).
방법1: 이 문제를 보고 첫 번째 반응은 돌아가는 방법으로 하는 것이다.
/**
* f(n)=f(n-1)+f(n-2)， ， 。
*/
public int climbStairs(int n) {
if (n == 0 || n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
return climbStairs(n - 1) + climbStairs(n - 2);
}
}방법2: 돌아가는 사상으로 한다.그러나 제출 방법이 끝나면 운행 시간이 초과됩니다.계속 분석한 결과 동적 기획의 사상을 이용하여 f[1..n]의 값을 수조로 저장할 수 있음을 발견했다.
/**
* ： s[i] i+1 ， 。 , 。
* s ， s[i] 。 s[i]=s[i-1]+s[i-2] 。
*/
public int climbStairs2(int n) {
if (n == 0 || n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
int s[] = new int[n];
s[0] = 1;
s[1] = 2;
for (int i = 2; i < n; i++) {
s[i] = s[i - 1] + s[i - 2];
}
return s[n - 1];
}
}방법3: 방법2에서 계산 효율을 크게 향상시켰지만 하나의 수조를 저장하는 것은 필요없다. 단지 세 개의 값만 저장하면 된다.첫 번째 i를 계산하려면 i-1과 i-2에 대응하는 값만 알면 된다.
/**
* 2 ， ，f3 = f1 + f2。
* f1 f3 ，f2 f3 。
*/
public int climbStairs3(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
int f1 = 1;
int f2 = 1;
int f3 = 0;
for (int i = 2; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
