자세한 사례 설명: 동적 프로그래밍 소개(계단을 예로 들어)

개념

동적 프로그래밍은 운영 연구의 한 분야이자 의사 결정 프로세스를 최적화하기 위한 수학적 방법입니다.
동적 프로그래밍 알고리즘은 일반적으로 재귀 공식과 하나 이상의 초기 상태를 기반으로 합니다. 현재 하위 문제의 해결책은 이전 하위 문제의 해결책에서 파생됩니다.

기본 아이디어

주어진 문제를 해결하려면 문제의 여러 부분을 해결한 다음(예: 하위 문제 해결) 하위 문제의 솔루션을 결합하여 원래 문제에 대한 솔루션을 얻어야 합니다.
보통 많은 하위 문제는 매우 유사하므로 동적 프로그래밍은 각 하위 문제를 한 번만 해결하여 계산량을 줄이려고 합니다.
주어진 하위 문제에 대한 해결책이 계산되면 메모리에 저장되어 다음에 동일한 하위 문제에 대한 해결책이 필요할 때 테이블을 직접 조회할 수 있습니다.
이 접근 방식은 입력 크기에 따라 반복되는 하위 문제의 수가 기하급수적으로 늘어날 때 특히 유용합니다.
동적 프로그래밍에는 세 가지 핵심 요소가 있습니다.
1. 최적의 하위 구조
2. 경계
3. 상태 전이 방정식

문제를 살펴보겠습니다.

문제

10개의 계단이 있습니다. 바닥 위로 올라가면 각 단계마다 1~2단계만 올라갈 수 있습니다. 총 몇 번의 움직임이 있는지 찾아보세요.

예를 들어 한 걸음씩, 총 10걸음이 걷는 방법 중 하나입니다.
또 다른 예는 매번 2걸음씩 걸어 총 5걸음이 되는 것입니다.

하지만 이걸 하나씩 하기에는 너무 번거롭습니다. 아래 그림과 같이 마지막 단계를 어떻게 밟아야 할지 생각만 하면 됩니다

10번째 계단으로 가는 길 = 8번째 계단으로 가기 + 10번째 계단으로 가기 9번째 계단
f(n)을 사용하여 n번째 계단에 도달하는 방법을 나타내므로 f(10) = f(9) + f(8)
그러면 f(9) = f(8) + f( 7), f(8) = f(7) + f(6)......

이런 식으로 우리는 재귀 공식을 얻습니다:
f(n) = f(n-1 ) + f(n-2);
또한 두 가지 초기 상태가 있습니다:
f(1) = 1;
f(2) = 2;

이것은 첫 번째 솔루션을 제공합니다

방법 1: 재귀적 해법

function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    return getWays(n-1) + getWays(n-2); 
}

이 방법의 시간 복잡도는O(2^n)

이진 트리임을 알 수 있으며, 노드 수가 우리의 재귀 횟수입니다. 방정식을 계산해야 하는데 숫자의 높이는 N이고 노드 수는 약 2^n
이므로 시간 복잡도는 약 O(2^n)

입니다. 그런데 이 방법을 최적화할 수 있을까요?

아래 그림과 같이 일부 값이 반복적으로 계산되는 것을 알 수 있습니다.

동일한 색상은 반복되는 부분을 나타내므로 이러한 반복 계산된 값을 기록할 수 있을까요? 이러한 최적화를 위한 두 번째 방법이 있습니다

방법 2: 메모 알고리즘

const map = new Map(); 
function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (map.has(n)) {
        return map.get(n);
    }
    const value = getWays(n-1) + getWays(n-2);
    map.set(n, value);
    return value; 
}

n-2 키-값 쌍은 결국 맵에 저장되므로 공간 복잡도는

O(n), 시간입니다. 복잡성도 O(n)

계속 생각해 보세요. 이것이 최적의 솔루션일까요?

다시 원래 생각으로 돌아가서 이전 계단을 걸었다고 가정하고 마지막 단계만 고려하면 f(n) = f(n-1) + f(n-)라는 재귀 공식을 얻을 수 있습니다. 2) 이것은 하향식 솔루션입니다.

일반적으로 일반적인 생각에 따라 단계적으로 올라가야 하며 일반 사람들의 생각과 더 일치하도록 아래에서 위로 해결해야 합니다.

이것은 앞서 언급한 초기 상태

인 1계단과 2계단의 계단 수 f를 구하는 반복입니다. (3)은 f(1)과 f(2)에만 의존합니다.

다음 단계를 계속 살펴보세요

계단의 4단계를 얻기 위해 여기서 또 다른 반복이 수행됩니다. f(4)는 f(2에만 의존합니다. ) 및 f (3)

각 반복에는 처음 두 반복의 데이터만 필요하며 메모처럼 모든 하위 상태의 데이터를 저장할 필요가 없다는 것을 발견했습니다

방법 3: 동적 프로그래밍 솔루션

function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    // a保存倒数第二个子状态数据，b保存倒数第一个子状态数据， temp 保存当前状态的数据
    let a = 1, b = 2;
    let temp = a + b;
    for (let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

이것이 바로 우리가 볼 수 있는 것입니다. 현재 시간 복잡도와 공간 복잡도

현재 시간 복잡도는 여전히
O(n)이지만, 공간 복잡도는 O(1)으로 감소합니다. 이것이 이상적인 결과입니다.

요약

이것은 동적 프로그래밍입니다. 변경 차원이 하나뿐이기 때문에 세상에서 가장 간단한 질문 중 하나입니다.

변경 차원이 2, 3 또는 그 이상이 되면 배낭 문제는 더 복잡해집니다. 일반적인 다차원 문제에 관심이 있으시면 온라인으로 "배낭 여행에 대한 9가지 강의"를 확인하세요

관련 권장 사항:

JS 동적 프로그래밍 사용에 대한 자세한 설명

JavaScript 고급 알고리즘 동적 프로그래밍 예제 분석

위 내용은 자세한 사례 설명: 동적 프로그래밍 소개(계단을 예로 들어)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!