백준 - 행렬 곱셈 순서 (11049)

let N = Int(readLine()!)!
var matrix = [[-1, -1]]
var dp = Array(repeating: Array(repeating: -1, count: N + 1), count: N + 1)

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    matrix.append(input)
}

print(execute(1, N))

func execute(_ s: Int, _ e: Int) -> Int {
    var result = Int.max
    
    if dp[s][e] != -1 {
        return dp[s][e]
    }
    if s == e {
        return 0
    }
    if s + 1 == e {
        return matrix[s][0] * matrix[s][1] * matrix[e][1]
    }
    for i in s..<e {
        result = min(result, matrix[s][0] * matrix[i][1] * matrix[e][1] + execute(s, i) + execute(i + 1, e))
    }
    dp[s][e] = result
    return result
}

i~j 구간의 행렬을 합치는 데 필요한 최소 곱셈 연산 횟수를 안다고 가정하고, 시작 행렬부터 끝 행렬까지 하나씩 범위를 늘려가면서 곱셈 연산 횟수를 구하고 그 최솟값을 dp 테이블에 저장한다.