LeetCode Day동적 프로그래밍 Part1

509. 피보나치 수

일반적으로 F(n)으로 표시되는 피보나치 수열은 피보나치 수열이라고 하는 수열을 형성하며, 각 수는 0과 1부터 시작하여 앞의 두 수의 합이 됩니다. 즉,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), n > 1.
n이 주어지면 F(n)을 계산합니다.

예 1:

입력: n = 2
출력: 1
설명: F(2) = F(1) + F(0) = 1 + 0 = 1.
예시 2:

입력: n = 3
출력: 2
설명: F(3) = F(2) + F(1) = 1 + 1 = 2.
예시 3:

입력: n = 4
출력: 3
설명: F(4) = F(3) + F(2) = 2 + 1 = 3.

제약사항:

0 원본페이지

재귀 방법

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

재귀 방법은 DFS와 유사하게 깊이 들어간 다음 역추적을 수행하여 최종 답을 얻습니다.
시간: O(2^n)
공간: O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n<2){
            dp[n] = n;
            return n;
        }  

        if(n>=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }

동일한 요소의 재발을 방지하기 위해 전역 배열을 사용하여 결과를 저장할 수 있습니다. 예를 들어 아래 그림은 f(17)과 f(18)이 두 개의 서로 다른 재귀 경로이고 일반적인 재귀 방법을 사용하는 경우 두 번 이상 계산해야 함을 보여줍니다.

시간: O(n), 공간: O(n)

동적 프로그래밍

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

재귀는 위에서 아래로 작동한 다음 역추적되며, 메모리 재귀는 이중 계산을 피하기 위해 재귀 결과를 저장합니다. 이제 동적 프로그래밍은 아래에서 위로 작동하며 각 단계의 결과를 dp 배열에 저장합니다.
시간: O(n)
공백: O(n)

또한 배열 대신 제한 숫자를 동적으로 업데이트할 수 있습니다. 이렇게 하면 특히 수많은 요소의 경우 공간 복잡성이 줄어듭니다.

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int start = 0;
        int pre = 1;
        int res = pre;

        for(int i=2; i<=n; i++){
            res = start + pre;
            start = pre;
            pre = res;
        }
        return res;
    }

70. 계단 오르기

당신은 계단을 오르고 있습니다. 정상에 도달하려면 n 단계가 필요합니다.

때마다 1~2계단씩 오를 수 있습니다. 얼마나 많은 방법으로 정상에 오를 수 있나요?

예 1:

입력: n = 2
출력: 2
설명: 정상에 오르는 방법은 두 가지가 있습니다.

1. 1단계 + 1단계
2. 2단계 예시 2:

입력: n = 3
출력: 3
설명: 정상에 오르는 방법은 세 가지가 있습니다.

1. 1단계 + 1단계 + 1단계
2. 1단계 + 2단계
3. 2단계 + 1단계

70. 계단 오르기

당신은 계단을 오르고 있습니다. 정상에 도달하려면 n 단계가 필요합니다.

때마다 1~2계단씩 오를 수 있습니다. 얼마나 많은 방법으로 정상에 오를 수 있나요?

예 1:

입력: n = 2
출력: 2
설명: 정상에 오르는 방법은 두 가지가 있습니다.

1. 1단계 + 1단계
2. 2단계 예시 2:

입력: n = 3
출력: 3
설명: 정상에 오르는 방법은 세 가지가 있습니다.

1. 1단계 + 1단계 + 1단계
2. 1단계 + 2단계
3. 2단계 + 1단계

제약사항:

1 원본페이지

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

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }

        int prepre = 1;
        int pre = 2;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = prepre + pre;
            prepre = pre;
            pre = res;
        } 
        return res;       
    }

746. 계단 오르기의 최소 비용

cost[i]가 계단의 i번째 계단의 비용인 정수 배열 비용이 주어졌습니다. 비용을 지불하고 나면 한 계단, 두 계단 올라갈 수 있습니다.

인덱스가 0인 단계부터 시작하거나 인덱스가 1인 단계부터 시작할 수 있습니다.

최상층에 도달하기 위한 최소 비용을 반환합니다.

예 1:

입력: 비용 = [10,15,20]
출력: 15
설명: 인덱스 1에서 시작합니다.

• 15달러를 지불하고 두 계단을 올라 정상에 도달하세요. 총 비용은 15입니다. 예시 2:

입력: 비용 = [1,100,1,1,1,100,1,1,100,1]
출력: 6
설명: 인덱스 0에서 시작합니다.

• 1을 지불하고 두 계단을 올라가면 지수 2에 도달합니다.
• 1을 지불하고 두 계단을 올라가면 지수 4에 도달합니다.
• 1을 지불하고 두 계단을 올라가면 지수 6이 됩니다.
• 1을 지불하고 한 단계 올라가면 지수 7이 됩니다.
• 1을 지불하고 두 계단을 올라가면 지수 9에 도달합니다.
• 1달러를 지불하고 한 계단만 올라가면 정상에 도달할 수 있습니다. 총 비용은 6입니다.

제약사항:

2 0 원본페이지

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length < 2){
            return 0;
        }

        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];

    }
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`

질문에서 인덱스 0과 인덱스 1에서 시작할 수 있다는 점을 주의하세요. 이는 계단 수가 2보다 작으면 해당 지점에서 시작할 수 있고 시작 동작이 변경되기 때문에 비용이 0이 된다는 것을 의미합니다. 비용 0, 이동 비용의 동작만 수행됩니다.

위 내용은 LeetCode Day동적 프로그래밍 Part1의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!