leetcode #70 계단 오르기 | 문제 푸는 길 두 번째 역 - 동적 기획 관련 문제
1155 단어 알고리즘 설계와 분석
문제 설명
만약 네가 계단을 오르고 있다면.n 단계가 있어야 옥상에 도착할 수 있습니다.
매번 너는 한 계단이나 두 계단을 올라갈 수 있다.너는 옥상까지 올라갈 수 있는 몇 가지 다른 방법이 있니?
주의: n을 정하는 것은 정수입니다.
예1:
： 2
： 2
： 。
1. 1 + 1
2. 2 예 2:
： 3
： 3
： 。
1. 1 + 1 + 1
2. 1 + 2
3. 2 + 1 문제풀이 사고방식-동적 기획
이 문제는 비교적 간단하다. n번째 계단에 대해 말하자면 두 가지 도착 방식이 있을 수 있다.
1 - n - 1계단을 지나 1계단을 올라가면 도착한다.
2-n-2계단을 지나 2단계를 올라가면 도착한다.
만약 우리가 n-1계단에 도달하는 것과 n-2계단에 도달하는 다른 방법수를 알고 있다면, 둘을 더하면 n계단에 도달하는 다른 방법수다.
문제는 다음과 같습니다.
1 - 첫 번째 계단에 도착하는 방법은 모두 1가지가 있다.
2 - 두 번째 계단에 도착하는 방법은 모두 두 가지가 있다.
그룹 ans[i]를 i번째 계단에 도착하는 다른 방법의 개수에 저장하려면
ans[ 1 ] = 1;
ans[ 2 ] = 2;
3 <=i <=n 시,
ans[ i ] = ans[ i - 1 ] + ans[ i - 2 ].
코드는 다음과 같습니다.
class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
vector ans(n+1);
ans[1] = 1;
ans[2] = 2;
for (int i = 3; i <= n; i++) {
ans[i] = ans[i - 1] + ans[i - 2];
}
return ans[n];
}
}; 시간 복잡도: O(n)
공간 복잡성: O(n)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 설계와 분석: 제4장 동적 기획 4.3 다단도의 가장 짧은 경로 문제/* 多段图的最短路径问题: 定义： 给定有向带权图G(V,E,W)，如果把顶点集合V划分成 k个不相交的子集V i ，1≤i ≤k，k≥2，使得E中的任何一条边 (u,v)，必有uЄ V i， v ∈ V i+m ，m≥1，则称这样的图为...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
