개구리 계단 뛰기 문제

제목 묘사: 개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급의 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해라.해석: 귀속과 동적 기획 두 가지 방법을 이용하여 귀속법을 구할 수 있다. 비교적 간단하다(코드 직접 붙이기)

/**
     *  
     *
     * @author [email protected]
     * @date 2018/11/13 22:11
     * @param n  
     * @return int
     **/
    public static int getNumJump(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return getNumJump(n-2) + getNumJump(n - 1);
    }

동적 계획:

 /**
     *  
     *
     * @author [email protected]
     * @date 2018/11/13 22:18
     * @param n  
     * @return int
     **/
    public static int getJumpWithDynamic(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }

        int a = 1;
        int b = 2;
        int temp = 0;
        /*  i=3  ，  i=n  。 ， 。
         a b， ，temp */
        for (int i = 3; i <= n; i ++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;

    }

테스트:

public static void main(String[] args) {
        // 
        System.out.println(" :" + getNumJump(12));

        // 
        System.out.println(" :" + getJumpWithDynamic(12));
    }

결과:

 :233
 :233

효율성 비교: