알고리즘 연구 노트(8) - 동적 프로그래밍의 기초

이 질문의 목표는 솔루션의 수를 찾는 것입니다.역추적을 통해 모든 가능성을 철저히 소진하는 것을 고려할 수 있습니다. . 구체적으로 계단 오르기를 여러 단계의 선택 과정으로 상상해 보세요. 바닥에서 시작하여 각 단계마다 한두 단계를 선택하고, 계단 꼭대기에 도달할 때마다 옵션 수에 1을 추가하고, 올라갈 때 옵션 수를 늘립니다. 당신은 계단 꼭대기에 도달했습니다.

코드 예：


# python代码示例
def backrack(choices,state,n,res) :
    if state == n :
        res[0] += 1 
    for choice in choices :
        if state + choice > n :
            continue
        backrack(choices,state+choice,n,res)
def climbing_stairs_backrack(n) :
    choices = [1,2]
    state = 0
    res = [0]
    backrack(choices,state,n,res)
    return res[0]
n = int(input())
print(climbing_stairs_backrack(n))


// c++代码示例
void backrack(vector<int> &choices, int state, int n, vector<int> &res)
{
    if (state == n )
    {
        res[0]++ ;
    }
    for (auto &choice : choices)
    {
        if (state + choice > n)
        {
            continue ;
        }
        backrack(choices, state + choice, n, res)
    }
}
 
int climbingStairsBackrack(int n)
{    
    vector<int> choices = {1 , 2 } ;
    int state = 0 ;
    vector<int> res = [0] ;
    backrack(choices, state, n, res) ;
    return res[0] ;
}

잔인한 검색:

역추적 알고리즘은 일반적으로 문제를 명시적으로 해체하지 않지만 문제를 일련의 의사 결정 단계로 처리하고 휴리스틱과 가지치기를 통해 가능한 모든 솔루션을 검색합니다.

우리는 문제 분해의 관점에서 이 질문을 분석해 볼 수 있습니다. i번째 레벨로 올라가기 위한 dp[i] 해가 있다고 가정하면 dp[i]가 원래 문제이고 하위 문제는 다음과 같습니다.

dp[i-1]，dp[i-2]，dp[1]，dp[2]

매 라운드마다 1, 2계단만 올라갈 수 있기 때문에 i번째 계단에 섰을 때 이전 라운드에서는 i-1, i-2계단에만 설 수 있었습니다. 즉, i-1 또는 i-2 수준에서 i-수준으로만 이동할 수 있습니다.

이로부터 우리는 중요한 추론을 할 수 있습니다. i-1 수준에 오른 계획 수와 i-2 수준에 오른 계획 수를 더한 것은 i 수준에 오른 계획 수와 같습니다. -레벨. 공식은 다음과 같습니다.

dp[i] = dp[i-1] + dp[i-2]

이는 건물 오르기 문제에는 재귀적 관계가 존재하며, 하위 문제의 해법을 구성함으로써 원래의 문제를 해결할 수 있음을 의미한다.

Dfs 코드 예: (검색)


# python 代码示例
def dfs(i : int) -> int :
    if i == 1 or i == 2 :
        return i
    count = dfs(i - 1) + dfs(i - 2)
    return count
def climbing_stairs_dfs(n : int) -> int :
    retunr dfs(n)


// c++ 代码示例
int dfs(int i)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    int count = dfs(i - 1) + dfs(i - 2);
    return count ;
}
int climbingStairsDFS(int n)
{
    retunr dfs(n) ;
}

폭력적인 재귀로 생성된 재귀 트리：

위에서 언급한 재귀 트리의 중복 문제를 해결하기 위해 메모리 탐색 방법을 사용하여 반복적으로 구성된 다수의 동일한 하위 트리를 제거함으로써 계산 효율성을 높일 수 있습니다. (중복되는 하위 문제）

메모된 검색:

겹치는 모든 하위 문제를 한 번만 계산하려면 nem 배열을 선언하여 각 하위 문제의 해를 기록하고 검색 프로세스 중에 겹치는 하위 문제를 정리해야 합니다.

dp[i]가 처음 계산되면 이후 사용을 위해 nem[i]에 기록됩니다.
dp[i]를 다시 계산할 때 하위 문제의 반복 계산을 피하기 위해 nem[i]에서 직접 결과를 얻습니다.

코드 예:


# python 代码示例
def dfs(i : int, mem : list[int]) -> int :
    if i == 1 or i == 2 :
        return i
    if mem[i] != -1 :
        return mem[i]
    count = dfs(i - 1, mem) + dfs(i - 2, mem)
    # 记录dfs(i)
    mem[i] = count
    return count
def climbing_stairs_dfs_mem(n : int) -> int :
    mem = [-1] * (n + 1)
    return dfs(n, mem)


// c++ 代码示例
int dfs(int i, vector<int> &mem)
{
    if (i == 1 || i == 2)
    {
        return i ;
    }
    if (mem != -1)
    {
        return mem[i] ;
    }
    int count = dfs(i - 1, mem) + dfs(i - 2, mem) ;
    mem[i] = count ;
    return count ;
}
int climbingStairsDFSMem(int n)
{
    vector<int> mem(n + 1, -1) ;
    return dfs(n, mem) ; 
}

메모한 후에는 겹치는 모든 하위 문제를 한 번만 계산하고 시간 복잡도는 O(n)으로 최적화됩니다.

동적 프로그래밍:

메모화된 검색은 원래 문제(루트 노드)에서 시작하여 가장 작은 알려진 하위 문제(리프 노드)를 해결할 때까지 더 큰 하위 문제를 더 작은 하위 문제로 재귀적으로 분해합니다. . 이후, 역추적을 통해 하위 문제에 대한 솔루션을 계층별로 수집하여 원래 문제에 대한 솔루션을 구성합니다.

대조적으로, 동적 프로그래밍은 "하단에서 상단까지" 접근 방식입니다. 즉, 가장 작은 하위 문제에 대한 솔루션부터 시작하여 원래 문제에 대한 솔루션을 얻을 때까지 더 큰 하위 문제에 대한 솔루션을 반복적으로 구축합니다.

동적 프로그래밍에는 역추적 프로세스가 포함되어 있지 않으므로 재귀를 사용하지 않고 루프 반복을 사용하여 구현하면 됩니다.

코드 예: (동적 프로그래밍, 가장 작은 하위 문제부터 시작)


# python 代码示例
def clibing_stairs_dp(n) :
    if n == 1 or n == 2 :
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3,n + 1) :
        dp[i] = dp[i-1] + dp[i- 2]
    return dp[n]


// c++ 代码示例
 
int climbingStairsDP(int n) 
{
    if (n == 1 || n == 2)
    {
        retunr n ;
    }
    vector<int> dp(n + 1, -1) ;
    dp[1] = 1 ;    
    dp[2] = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        dp[i] = dp[i - 1] + dp[i- 2] ;
    }
    return dp[n] ;
}

실행 프로세스(동적 프로그래밍):

분석: (동적 프로그래밍)

역추적 알고리즘과 마찬가지로 동적 프로그래밍도 "상태" 개념을 사용하여 문제 해결의 특정 단계를 나타냅니다. 각 상태는 하위 문제 및 해당 로컬 최적 솔루션에 해당합니다. 예: 계단 오르기 문제의 상태는 현재 계단의 차수 i로 정의됩니다.

위의 내용을 바탕으로 동적 용어에 대한 일반적인 용어를 요약할 수 있습니다.

dp 배열은 {dp table}이라고 하며, dp[i]는 상태 i에 해당하는 하위 문제에 대한 솔루션을 나타냅니다.
최소 하위 문제(첫 번째 및 두 번째 계단)에 해당하는 상태를 초기 상태라고 합니다.
재귀 공식 dp[i] = dp[i-1] + dp[i-2]를 상태 방정식이라고 합니다.

공간 최적화:

dp[i]는 dp[i-1] 및 dp[i-2]에만 관련됩니다.

모든 하위 문제에 대한 솔루션을 저장하기 위해 배열을 사용하는 대신 앞으로 스크롤하려면 두 개의 변수만 필요합니다.

코드 예:


# python 代码示例
def clibing_stairs_dp_comp(n) :
    if n == 1 or n == 2 :
        return n
    a, b = 1, 2
    for _ in range(3, n + 1) :
        a, b = b , a + b
    return b


// c++ 代码示例
int climbingStairsComp(int n) 
{
    if (n == 1 || n == 2)
    {
        return n ;
    }
    int a = 1 , b = 2 ;
    for (int i = 3 ; i <= n ; i++)
    {
        int temp = b ;
        b = a + b ;
        a = temp ;
    }
    return b ;
}

분석:

배열 dp가 차지하는 공간은 생략되고, 공간 복잡도는 O(n)에서 O(1)로 감소됩니다.

동적 프로그래밍 문제에서 현재 상태는 제한된 수의 이전 상태에만 관련되어 있으며, 이때 "차원 축소"를 통해 필요한 상태만 유지하고 메모리 공간을 절약할 수 있습니다. . 이 공간 최적화 기술을 "롤링 변수" 또는 "롤링 배열"이라고 합니다.

기술나눔