algo306

306.swift

let aa = [3, 1, 4, 1, 5, 9, 2, 6]
func getInt2() -> (Int, Int) { (aa.count, 4) }
func getIntArray() -> [Int] { aa }

///
let (n, m) = getInt2()
let a = getIntArray()

var dp = Array<Int?>(repeating: nil, count: n)
dp[0] = 0
func resolve(_ n: Int) -> Int {
    
    if let k = dp[n] {
        
        return k
    }
    
    let d = n > m ? m : n
    let k = (1...d)
        .reduce(Int.max) { min($0, resolve(n - $1) + $1 * a[n]) }
    dp[n] = k
    return k
}

print(
    resolve(n - 1)
)