Climbing Stairs(계단 오르기 문제)
1287 단어 LeetCode
이것은 매우 고전적이고 간단한 귀속 문제다.정정수 n을 계단의 계수로 정하고 매번 한 걸음 또는 두 걸음 올라갈 수 있으며 몇 가지 계단을 오르는 방법이 있는지 물어본다.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step2. 귀속 방법
처음에 나는 귀속적인 방법으로 썼는데 코드는 매우 간단하지만 시간의 복잡도가 매우 높았다.
class Solution {
public int climbStairs(int n) {
if(n == 1)
return 1;
if(n == 2)
return 2;
reuturn climbStairs(n - 1) + climbStairs(n - 2);
}
}3. 동적 기획
동적 계획을 바꾸면 시간의 복잡도가 떨어질 수 있다.관찰 결과 실제로 우리가 n보를 계산할 때 n-1보와 n-2보만 사용했기 때문에 우리는 길이가 2인 수조를 가지고 앞의 두 단계를 계단으로 올라가는 방법을 보존하면 된다.
class Solution {
public int climbStairs(int n) {
int[] steps = new int[2];
steps[0] = 1;
steps[1] = 2;
for(int i = 3;i <= n;i ++){
if(i % 2 == 1)
steps[0] += steps[1];
else
steps[1] += steps[0];
}
if(n % 2 == 1)
return steps[0];
return steps[1];
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
