이 계단을 오르는 프로그래밍 문제를 너는 풀 수 있니?(귀속과 교체 사상)

면접 문제:
프로그래밍 문제: n개의 계단이 있는데, 한 번에 한 걸음 또는 두 걸음만 올라갈 수 있으며, 모두 몇 가지 걸음걸이가 있습니까?
고찰의 지식점:
귀속과 순환의 교체
귀속:
n의 값
길을 걷다
산식
일
한 번에 한 걸음만
f(1) = 1
이
(1) 한 번에 1보 (2) 직접 2보
f(2) = 2
삼
(1) f(1)에 먼저 도착한 경우, f(1)에서 직접 2단계(2)에 먼저 도착한 경우, f(2)에서 직접 1단계
f(3) = f(2) + f(1) = 3
사
(1) f(2)에 먼저 도착한 경우, f(2)에서 직접 2단계(2)에서 f(3)에 먼저 도착한 경우, f(3)에서 직접 1단계
f(4) = f(3) + f(2) = 5
...
...
...
n = x
(1) f(n-2)에 먼저 도착한 경우, f(n-2)에서 직접 2단계(2) f(n-1)에 먼저 도착한 경우, f(n-1)에서 직접 1단계
f(x) = f(x - 2) + f( - 1)
반복 방식의 예제 코드:

public class DiGuiTest {
    public static int diGui(int n) {
        if (n < 1) {
            throw new IllegalArgumentException(n + " 1");
        }
        if (n == 1 || n == 2) {
            return n;
        }
        return diGui(n - 1) + diGui(n - 2);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(diGui(40)); // 165580141
        long end = System.currentTimeMillis();
        System.out.println(" ：" + (end - start)); // 633ms
    }
}

순환 교체:
one 저장 마지막 1단계, two 저장 마지막 2단계.순환 교체는 이 두 변수 (one, two) 의 값을 끊임없이 수정하는 것이다.
n의 값
길을 걷다
산식
일
한 번에 한 걸음만
f(1) = 1
이
(1) 한 번에 1보 (2) 직접 2보
f(2) = 2
삼
(1) f(1)에 먼저 도착한 경우, f(1)에서 직접 2단계(2)에 먼저 도착한 경우, f(2)에서 직접 1단계
f(3) = two + onef(3) = f(1) + f(2)two = f(2); one = f(1)
사
(1) f(2)에 먼저 도착한 경우, f(2)에서 직접 2단계(2)에서 f(3)에 먼저 도착한 경우, f(3)에서 직접 1단계
f(4) = two + onef(4) = f(2) + f(3)two = f(2); one = f(3)
...
...
...
n = x
(1) f(n-2)에 먼저 도착한 경우, f(n-2)에서 직접 2단계(2) f(n-1)에 먼저 도착한 경우, f(n-1)에서 직접 1단계
f(x) = two + onef(x) = f(x - 2) + f(x - 1)two = f(x - 2); one = f(x - 1)
반복 방식의 예제 코드:

public class XunHunDieDaiTest {
    public static int xunHunDieDai(int n) {
        if (n < 1) {
            throw new IllegalArgumentException(n + " 1");
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int one = 1; //  
        int two = 2; //  
        int sum = 0;

        for (int i = 3; i <= n; i++) {
            sum = two + one;
            one = two;
            two = sum;
        }

        return sum;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(xunHunDieDai(40)); // 165580141
        long end = System.currentTimeMillis();
        System.out.println(" ：" + (end - start)); // < 1ms
    }
}

비교 요약:
방법은 자신을 귀속이라고 부르고 변수의 원값을 이용하여 새로운 값을 내놓는 것을 교체라고 부른다.
귀속:

장점: 큰 문제가 작은 문제로 바뀌면 코드의 양을 줄일 수 있고 코드가 더욱 간소화되고 가독성이 좋다

단점: 귀속 호출은 공간을 낭비하고 귀속이 너무 깊으면 창고가 넘치기 쉽다

순환 교체:

장점: 코드 운행 효율이 좋다. 시간은 순환 횟수 증가로만 증가하고 추가 공간 비용이 없기 때문이다

.단점: 코드는 귀속이 간결하지 않고 가독성이 좋지 않다..
개인 블로그에 오신 것을 환영합니다.https://wenshixin.gitee.io/blog/