LeetCode(70)Climbing Stairs
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?
분석은 다음과 같습니다.
여기 이 댓글이 잘 쓰여 있는 것을 보고 바로 붙였다.This is just Fibonacci numbers. The number of distinct ways for n steps are the sum of distinct ways for n-1 (because we can move 1 step first, then move the rest n - 1 steps) and distinct ways for n - 2 (because we can move 2 steps first, there are two ways to do it: move 1 steps twice and move 2 steps once, the former is a duplicate for the n - 1 case so we should eliminate).
코드는 다음과 같습니다.
class Solution {
public:
int climbStairs(int n) {
int a1=1;
int a2=2;
int sum=0;
if(n==1)
return 1;
if(n==2)
return 2;
for(int i=3;i<=n;i++){
sum=a1+a2;
a1=a2;
a2=sum;
}
return sum;
}
};소결:
(1) 본 문제는 먼저 그림을 그려보고 문제의 본질이 피보나치 수열구통항 공식이라는 것을 알아야 한다.나는 먼저 귀속을 써서 제출 발견 시간을 초과했다.귀속이 교체보다 더 많은 시간과 공간 비용을 증가시킬 수 있음을 감안하여 귀속으로 바꾸면 절차가 통과된다.
2014-10-06 update:
본질은 위와 같다. 단지 업데이트 후 수조 steps로 결과를 저장할 뿐, 위에서 a1, a2,sum를 번갈아 저장하는 방식보다 읽기 쉽다.
class Solution {
public:
int climbStairs(int n) {
int* steps = new int[n + 1];
steps[1] = 1;
steps[2] = 2;
for (int i = 3; i <= n; ++i) {
steps[i] = steps[i - 1] + steps[i - 2];
}
return steps[n];
}
};이 제목과 비교적 비슷하다.Leetcode (94) Unique Binary Search Trees
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
