올가미

공통적인 특징은 현재 값은 앞의 두 개 또는 앞의 몇 개의 특정한 위치의 값으로 유도할 수 있다는 것이다.

주의점

스택 오버플로우(StackOverflow)가 나타나면 귀속은 정방향 순환 구해로 바뀝니다.한 마디로 하면 정방향 순환 구해를 추천하고 정방향 구해가 더 좋다.모든 귀환은 정방향 순환으로 실현될 수 있다.

귀환은 필수적이며 코드의 양이 가장 적고 가장 좋은 것을 먼저 고려해야 한다.

카탈로그

계단 뛰어넘기

변태 계단 뛰어넘기

직사각형 덮어쓰기

피보나치 수열

로봇의 운동 범위

계단을 뛰어넘다

개구리 한 마리는 한 번에 1계단을 올라갈 수도 있고 2계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.

public int JumpFloor(int target) {
    if (target <= 0) return 0;
    if (target == 1 || target == 2) {
        return target;
    }
    return JumpFloor(target - 1) + JumpFloor(target - 2);
}

변태가 계단을 뛰어넘다

개구리 한 마리가 한 번에 1계단을 올라갈 수도 있고, 2계단을 올라갈 수도 있다.이 개구리가 n급 계단을 뛰어오르는 데는 모두 몇 가지 점프법이 있는지 구해 보세요.

사고방식 분석:

f1 = 1 f2 = f1 + 1 = f1 * 2 f3 = f2 + f1 + 1 = f2 * 2 f4 = f3 + f2 + f1 + 1 = f3 * 2 를 n > 1 로 지정하면 fn = f (n - 1) * 2

public int JumpFloorII(int target) {
    if (target <= 0) return 0;
    int ans = 1;
    for (int i = 1; i < target; i++) {
        ans *= 2;
    }
    return ans;
}

직사각형 덮어쓰기

우리는 21의 작은 직사각형을 가로로 하거나 세로로 더 큰 직사각형을 덮을 수 있다.실례지만 n개의 21개의 작은 직사각형으로 2*n의 큰 직사각형을 중첩 없이 덮어쓰는데 모두 몇 가지 방법이 있습니까?

최우해: 귀속 호출 f(n)=f(n-1)+f(n-2), 정방향 순환 구해

로 개선

public int RectCover(int target) {
    if (target <= 0) return 0;
    if (target == 1) return 1;
    if (target == 2) return 2;
    return RectCover(n - 1) + RectCover(n - 2);
}

public int RectCover(int target) {
    if (target <= 0) return 0;
    int a = 1, b = 2;
    for (int i = 1; i < target; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return a;
}

피보나치 수열

모두 피보나치 수열을 알고 있습니다. 지금 정수 n을 입력해야 합니다. 피보나치 수열의 n항을 출력해 주십시오.n<=39

public int Fibonacci(int n) {
    if (n <= 0) return 0;
    int a = 1, b = 1;
    for (int i = 1; i < n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return a;
}

로봇의 운동 범위

제목은 바닥에 m행과 n열의 네모난 칸을 묘사한다.한 로봇이 좌표 0, 0의 칸에서 이동하기 시작하는데 매번 왼쪽, 오른쪽, 위, 아래 네 방향으로만 한 칸을 이동할 수 있지만 행 좌표와 열 좌표의 수위의 합이 k보다 큰 칸에 들어갈 수 없다.예를 들어 k가 18일 때 로봇은 격자(35,37)에 들어갈 수 있다. 왜냐하면 3+5+3+7=18이기 때문이다.그러나 3+5+3+8=19 때문에 격자(35,38)에 들어갈 수 없다.이 로봇은 몇 개의 칸에 도달할 수 있습니까?

public int movingCount(int threshold, int rows, int cols) {
    int[][] flag = new int[rows][cols];
    return helper(threshold, flag, 0, 0, rows, cols);
}

private int helper(int key, int[][] flag, 
                   int i, int j, int rows, int cols) {
    if (i > rows - 1 || j > cols - 1 
        || flag[i][j] == 1 || numSum(i) + numSum(j) > key) {
        return 0;
    }
    flag[i][j] = 1;
    return helper(key, flag, i + 1, j, rows, cols)  + helper(key, flag, i, j + 1, rows, cols) + 1;
}

private int numSum(int i) {
    int sum = 0;
    do {
        sum += i % 10;
    } while ((i /= 10) > 0);
    return sum;
}