C++ Dynamic Programming 꿀팁

다음과 같이 코드를 짜면, memoization DP를 전역 변수 없이, 불필요하게 많은 함수 인자 없이 안전하게 짤 수 있다.

#include <bits/stdc++.h>

int main() {
    std::vector memo(100, std::optional<int>());
    
    std::function<int(uint32_t)> fibonacci = [&fibonacci, &memo](uint32_t i) -> int {
        if (memo[i].has_value()) {
            return memo[i].value();
        }
        return i <= 1 ? i : memo[i].emplace(fibonacci(i - 1) + fibonacci(i - 2));
    };
    
    std::cout << fibonacci(10) << std::endl;
        
}; // 55

이 코드에 적용된 여러 가지 트릭은 다음과 같다.

1. 템플릿 타입 추론(C++17) : memo의 타입은 std::vector<std::optional<int>>지만, <> 안에 있는 것을 적어줄 필요 없이 std::vector만 적어도 memo 생성자의 2번째 인자 타입으로부터 컴파일러가 알아서 타입을 생성해 준다.

마찬가지로 다음과 같이 3중 벡터를 간편하게 짤 수도 있다.

std::vector memo(100, std::vector(100, std::vector(100, -1)));

2. 람다 재귀함수 : 람다함수로도 재귀함수를 짤 수 있다. 람다의 타입을 std::function으로 명시해 준 뒤, 캡처 리스트에 본인의 참조자를 넣어 준다.

3. std::optional<T>(C++17) : 값이 있을 수도 있고 없을 수도 있는 상황을 나타내는 객체. 사실 fibonacci 같이 우리가 잘 알고 있는 재귀함수들은 memo의 initialization으로 -1 같은 음수 값을 넣어 줘도 괜찮지만, 함수의 리턴값의 범위를 잘 모른다면 std::optional<T> 객체를 써 주는 것이 안전할 것이다.