C++LeetCode 실현(70.계단 오 르 기 문제)

[LeetCode]70.계단 오 르 기 문제
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?
Note: Given n will be a positive integer.
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 step
이 블 로 그 는 처음에 이름 이 사다리 오 르 기 문제 라 고 불 렸 는데 항상 어린이 신발 이 블 로 거 에 게 모 바 일 에서 이 블 로 그 를 열지 못 한 다 는 것 을 보 여 주 었 다.블 로 거 는 매우 이상 하 다 고 생각 하고 자신 도 해 보 았 지만 과연 열 리 지 않 았 다.이 블 로그 자체 에 문제 가 있 는 것 이 아니 냐 는 생각 에 같은 댓 글 을 하나 더 올 리 려 고 했 는데 도 열 리 지 않 아 귀신 이 곡 할 노 릇 이 었 다.그래서 블 로 거들 이 이름 을 바 꿨 는데 열 렸 다 고?!조사 한 결과'사다리 타기'라 는 세 글자 가 민감 한 단어 인 것 을 알 게 되 었 습 니 다.제목 에 넣 으 면 블 로그 가 차단 되 었 습 니 다.저도 정말 취 했 습 니 다.총 에 누 워 있 는 것 이 좋 습 니까?어 쩔 수 없 이 계단 오 르 기 문제 로 이름 을 바 꿀 수 밖 에 없 었 습 니 다-|||.
이 사다리 오 르 기 문 제 는 처음에 무엇 을 시 키 는 지 몰 랐 다.나중에 다른 사람의 분석 을 보고 나 서 야 알 게 되 었 다.실제로 피 보 나치 수열 과 매우 비슷 하 다.사다리 가 n 층 이 있다 고 가정 하면 n 층 까지 어떻게 올 라 갈 수 있 을 까?매번 1 걸음 이나 2 걸음 만 올 라 갈 수 있 기 때문에 n 층 까지 올 라 가 는 방법 은 n-1 층 에서 한 걸음 올 라 오 거나 n-2 층 에서 2 걸음 올 라 오 는 것 이다.그래서 전달 공식 은 dp[n]=dp[n-1]+dp[n-2]를 쉽게 얻 을 수 있 습 니 다.피 보 나 계 액 수열 의 구 해 는 재 귀 를 사용 할 수 있 기 때문에 블 로 거들 은 가장 먼저 재 귀 를 시 도 했 고 OJ 에서 실 행 했 습 니 다.Time Limit Exceed 를 표시 합 니 다.즉,운행 시간 이 초과 되 었 습 니 다.재 귀 는 여러 가지 로 계산 되 었 기 때문에 효율 이 낮 습 니 다.여 기 는 동적 계획(Dynamic Programming)으로 효율 을 높 여야 합 니 다.코드 는 다음 과 같 습 니 다.
C++해법 1:

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        vector<int> dp(n);
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp.back();
    }
};

자바 해법 1:

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

우 리 는 공간 을 더욱 최적화 시 킬 수 있다.두 개의 정형 변수 a 와 b 로 과정 값 을 저장 할 수 있다.먼저 a+b 의 값 을 b 에 게 부여 한 다음 에 a 의 값 을 원래 의 b 로 부여 하기 때문에 b-a 로 할당 하면 된다.이렇게 하면 위의 누적 과정 을 모 의 했 고 모든 값 을 저장 하지 않 아 도 됩 니 다.코드 는 다음 과 같 습 니 다.
C++해법 2:

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        while (n--) {
            b += a;
            a = b - a;
        }
        return a;
    }
};

자바 해법 2:

public class Solution {
    public int climbStairs(int n) {
        int a = 1, b = 1;
        while (n-- > 0) {
            b += a; 
            a = b - a;
        }
        return a;
    }
}

앞에서 말 했 듯 이 재 귀적 인 표기 법 은 시간 을 초과 할 수 있 지만 기억 배열 을 더 하면 달라 집 니 다.기억 배열 은 계 산 된 결 과 를 저장 할 수 있 기 때문에 중복 계산 이 존재 하지 않 고 운행 효율 을 크게 향상 시 켰 습 니 다.사실은 재 귀적 인 기억 배열 과 반복 되 는 DP 형식 은 대체적으로 대동소이 합 니 다.참조 코드 는 다음 과 같 습 니 다.
C++해법 3:

class Solution {
public:
    int climbStairs(int n) {
        vector<int> memo(n + 1);
        return helper(n, memo);
    }
    int helper(int n, vector<int>& memo) {
        if (n <= 1) return 1;
        if (memo[n] > 0) return memo[n];
        return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    }
};

Java 해법 3:

public class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return helper(n, memo);
    }
    public int helper(int n, int[] memo) {
        if (n <= 1) return 1;
        if (memo[n] > 0) return memo[n];
        return memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
    }
}

포럼 에 분 치 법 Divide and Conquer 의 해법 도 있 습 니 다.재 귀 형식 으로 통과 할 수 있 습 니 다.하지만 블 로 거들 은 잘 이해 하지 못 했 습 니 다.여러분 의 관람석 신 들 이 블 로 거들 에 게 이 야 기 를 해 주 셨 으 면 좋 겠 습 니 다~
C++해법 4:

public class Solution {
    public int climbStairs(int n) {
        if(n <= 1) return 1;       
        return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
    }
}

자바 해법 4:

public class Solution {
    public int climbStairs(int n) {
        if(n <= 1) return 1;       
        return climbStairs(n / 2) * climbStairs(n - n / 2) + climbStairs(n / 2 - 1) * climbStairs(n - n / 2 - 1);
    }
}

사실 피 보 나치 수열 은 통 항 공식 을 구 할 수 있 습 니 다.추리 과정 은 위 에 있 는 이 스티커 를 참조 하 십시오.그러면 통 항 공식 이 있 으 면 상수 급 의 시간 복잡 도 범위 에서 결 과 를 구 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
C++해법 5:

class Solution {
public:
    int climbStairs(int n) {
        double root5 = sqrt(5);
        return (1 / root5) * (pow((1 + root5) / 2, n + 1) - pow((1 - root5) / 2, n + 1));
    }
};

자바 해법 5:

public class Solution {
    public int climbStairs(int n) {
        double root5 = Math.sqrt(5);
        double res =  (1 / root5) * (Math.pow((1 + root5) / 2, n + 1) - Math.pow((1 - root5) / 2, n + 1));
        return (int)res;
    }
}

여기 서 C++실현 LeetCode(70.계단 오 르 기 문제)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++실현 계단 오 르 기 문제 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!