동적 계획: 개구리 계단 뛰 기, 변태 계단 뛰 기

개구리 가 계단 을 뛰 어 넘 는 문 제 는 간단 한 동적 계획 문제 이다.
질문 1: 보통 계단 뛰 기
개구리 한 마리 가 한 번 에 한 계단 을 뛰 어 넘 거나 한 번 에 두 계단 을 뛰 어 넘 을 수 있다. 예 를 들 어:
4. 567917. 1 급 계단 에 뛰 어 오 르 는 방법 은 한 가지 방법 만 있다. 바로 1 급 을 뛰 면 된다
4. 567917. 2 급 계단 에 뛰 어 오 르 면 두 가지 점프 방법 이 있다. 매번 1 급 을 뛰 고 두 번 뛴다.아니면 한 번 에 2 급 뛰 기..
-- n 계단 을 뛰 어 올 라 가 려 면 몇 가지 점프 법 이 있 나.
많은 사람들 이 긍정 적 으로 생각 하고 폭력 적 으로 해결 하 는 것 을 좋아 하지만 복잡 한 문제 이다.우 리 는 거꾸로 생각 할 수 있다.
만약 우리 가 n 계단 을 뛰 어 올 라 가 려 고 한다 면 어떻게 뛰 어야 합 니까?이때 문 제 는 훨씬 간단 하 다. 정 답 은 n - 1 단계 에서 한 단계 뛰 어 올 라 가 거나 n - 2 단계 에서 두 단계 뛰 어 올 라 가 는 것 이다. 그 밖 에 개 구 리 는 n 단계 로 뛰 어 올 라 갈 수 있 는 다른 방법 이 없다.
우 리 는 f (n) 에 게 1 급 계단 에서 n 급 계단 으로 뛰 어 오 르 는 데 몇 가지 방법 이 있다 고 명령 했다.다음 과 같은 전달 공식 이 있다.
f(n)=f(n−1)+f(n−2)
익숙 하 죠?
피 보 나치 수열 이 요? 코드 는 간단 해 요.

int jumpFloor(int number) {
    int g = 1, f = 2;
    while (number-- > 1) {
        f += g;
        g = f - g;
    }
    return g;
}

질문 2: 변태 계단 뛰 어 내리 기
변태 가 계단 을 뛰 어 넘 는 문 제 는 다음 과 같다. 개구리 가 한 번 에 1 급 을 뛸 수도 있 고 한 번 에 2 급 을 뛸 수도 있 고 한 번 에 3 급 을 뛸 수도 있다.-- n 계단 을 뛰 어 올 라 가 려 면 몇 가지 점프 법 이 있 나.
마찬가지 로 우 리 는 역방향 사 고 를 통 해 문 제 를 n 급 계단 을 오 르 려 면 어떻게 뛰 어야 합 니까?답 은 다음 과 같다.
n 계단 을 뛰 어 올 라 가 려 면 n - 1 계단 에서 한 번 에 뛰 어 올 라 갈 수도 있 고 n - 2 계단 에서 한 번 에 뛰 어 올 라 갈 수도 있 고 n - 3 계단 에서 한 번 에 뛰 어 올 라 갈 수도 있 고... 1 계단 에서 한 번 에 뛰 어 올 라 갈 수도 있다.그러면 문 제 는 매우 간단 하 다. 마찬가지 로 f (n) 는 1 급 계단 에서 n 급 계단 으로 뛰 어 오 르 는 데 몇 가지 방법 이 있다 는 것 을 나타 낸다.다음 과 같은 전달 공식 이 있다.
f(n)=f(n−1)+f(n−2)+...+f(1)
동시에
f (n - 1) 도 다음 과 같다.
f(n−1)=f(n−2)+f(n−3)+...+f(1)
그래서 위의 두 공식 에서 알 수 있다.
f(n)=2f(n−1)=4f(n−2)=8f(n−3)=...
즉:
f(n)=2f(n−1)=22f(n−2)=23f(n−3)=...=2n−1f(n−(n−1))=2n−1f(1)
... 때문에
그래서
f(n)=2n−1 。
코드 는 다음 과 같 습 니 다:

int square(int a) { return a * a; }
int power2(int n) { //   2 n  
    if (0 == n) return 1;
    return n % 2 ? square(power2(n>>1))<<1 : square(power2(n>>1));
}

int jumpFloorII(int number) {
    return power2(number - 1);
}