DP 역추적 하기

문제 & 재정의

 

2662번: 기업투자

이전의, 인덱스로 상태관리하기 글의 문제와 동일하다.

---

Tabulation으로 DP

Tabulation으로 DP를 하게 되면, 상태 공간을 적층식으로 만들어 가게 된다.

즉, 현재 상태공간이 어느 상태공간에서 전이 됐는지 로직상에서 확인이 된다.

이는 적층식으로 전이 되는 과정에서, Path도 전이시켜 따로 관리하면 단순하게 해결할 수 있다.

dp = [[0] * (n+2) for _ in range(m+2)]
path = [[0] * (n+2) for _ in range(m+2)]

for i in range(1, m+1):
    for j in range(1, n+1):
        dp[i][j] = dp[i-1][j]

        for k in range(1, j+1):
            if dp[i][j] < (tmp := values[k][i] + dp[i-1][j-k]):
                dp[i][j] = tmp
                path[i][j] = k

tmp = n
result = []
for i in range(m, 0, -1):
    picked = path[i][tmp] 
    result.append(picked)
    tmp -= picked

print(dp[m][n])
print(*result[::-1])

---

Memorization으로 DP

Mermorization으로 DP를 하게 되면, 상태공간의 부분 상태 공간에서 전이 된다.

상태공간의 전이 부분을 로직상에서 확인을 할 수 없다.

하지만, (A+1) 상태는 (A)상태에서 전이 되었다는 것은 확실하기 때문에 이를 근거로 역추적을 할 수 있다.

(A+1) 상태와  A상태의 값이 같다면, 현재 상태에서 선택을 하지 않은 것이고,

값이 다르다면, 현재 상태(A+1)에서 선택을 했다는 것이다.

어느 값을 뽑아야 이전 상태(A)에서 현재 상태(A+1)에 올 수 있는지 연산하면 된다.

def invest(company_idx: int, capacity: int) -> int:
    if company_idx == m\
            or company_idx < 0:
        return 0
    
    if (ret := cache[company_idx][capacity]):
        return ret
    
    ret = invest(company_idx+1, capacity)

    for money in range(1, capacity+1):
        ret = max(ret,
                  invest(company_idx+1, capacity-money)
                  + company_invest[money-1][company_idx])
    
    cache[company_idx][capacity] = ret
    return ret


def reconstruct(company_idx: int, capacity: int) -> None:
    if company_idx == m:
        return
    
    if invest(company_idx, capacity) == invest(company_idx+1, capacity):
        picked.append(0)
        reconstruct(company_idx+1, capacity)
    
    else:
        for i in range(1, capacity+1):
            if (company_invest[i-1][company_idx] + invest(company_idx+1, capacity-i))\
                    == invest(company_idx, capacity):
                picked.append(i)
                reconstruct(company_idx+1, capacity-i)
                break