[Leetcode] 70. 계단 오 르 기

제목.
계단 을 오 르 고 있다 고 치자.n 단계 가 있어 야 옥상 에 도착 할 수 있 습 니 다.
매번 한 계단 이나 두 계단 을 올 라 갈 수 있다.당신 은 몇 가지 다른 방법 으로 옥상 까지 올 라 갈 수 있 습 니까?
주의: 주어진 n 은 정수 입 니 다.
예시 1:

  ： 2
  ： 2
  ：            。
1.  1   + 1  
2.  2

예시 2:

  ： 3
  ： 3
  ：            。
1.  1   + 1   + 1  
2.  1   + 2  
3.  2   + 1

해제
이 문 제 는 시 뮬 레이 션 만 하면 기본적으로 TP 라 고 생각 할 수 있 고 상태 방정식 을 쓰 면 피 보 나치 수열 이다.dp [i] = dp [i - 1] + dp [i - 2] i - 1 때 한 걸음 뛰 면 ii - 2 때 한 걸음 뛰 면 i - 1, 이게 dp [i - 1] 의 하위 문제 가 되 었 습 니 다. 두 걸음 뛰 면 i 에 도착 할 수 있 습 니 다.
java

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

python

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1 for i in range(n + 1)]
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다