알고리즘 문제: 계단 등반 문제
858 단어 알고리즘
이 문 제 는 Solution 에서 폭력 적 인 해결 에서 피 보 나치 와 알고리즘 최적화 까지 여섯 가지 해법 을 포함한다.
여기에 하나의 사고방식 이 추가 되 었 다. 조합 수
계단 을 오 르 는 문 제 는 한 걸음, 두 걸음 의 걷 기 가 최종 적 으로 결승점 에 도달 하 는 것 이다.
n 개의 공 을 얻 는 것 으로 추상 화 할 수 있 고 한 번 에 두 개 를 얻 을 수 있 으 며 한 번 에 하 나 를 얻 을 수 있 으 며 최종 적 으로 다 얻 을 때 까지 모두 얼마나 많은 방법 이 있 습 니까?
1 개 2 와 (n - 2) 개 1... n / 2 개 2 와 (n - n / 2) 개 1 의 배열 조합 수 를 합 친 코드 는 다음 과 같다.
class Solution(object):
def climbStairs(self, n):
count = 0
for i in xrange(0, n//2+1):
count += self.cni(n-i, i)
return count
def cni(self,n,i):
result = 1
for j in range(0, i):
result = result * (n-j) // (j+1)
return result
공간 복잡 도 O (1), 시간 복잡 도 O (n ^ 2) 는 피 보 나치 보다 간편 하지 못 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
