algo41

41.swift

let aa: [[Int]] = [
    [768, 527, 845],
    [978, 444, 266],
    [777, 746, 419],
    [109, 58, 54],
    [544, 391, 391],
    [937, 308, 901],
    [105, 310, 594],
    [830, 795, 221],
    [792, 547, 688],
    [699, 669, 856],
    [115, 688, 501],
    [135, 62, 396],
    [441, 894, 529],
    [774, 279, 539],
    [729, 352, 644],
    [105, 816, 984],
    [845, 960, 828],
    [867, 442, 214],
    [14, 786, 50],
    [123, 785, 944],
    [259, 668, 20],
    [571, 805, 576],
    [504, 836, 199],
    [760, 374, 940],
    [650, 54, 294],
    [603, 749, 279],
    [260, 911, 563],
    [864, 261, 949],
    [202, 775, 794],
]
func getInt() -> Int { aa.count }
func getIntArrayArray(_ i: Int) -> [[Int]] { aa }

///
let n = getInt()
let a = getIntArrayArray(n)

var dp = Array<Array<Int?>>(repeating: Array<Int?>(repeating: nil, count: 3), count: n)

func solve(_ i: Int, _ j: Int) -> Int {
    
    if i == 0 {
        
        return a[0][j]
    }
    
    if let k = dp[i][j] {
        
        return k
    }
    
    let k = a[i][j] + max(solve(i - 1, (j + 1) % 3), solve(i - 1, (j + 2) % 3))
    dp[i][j] = k
    
    return k
}
print(
    max(max(solve(n - 1, 0), solve(n - 1, 1)), solve(n - 1, 2))
)