https://algo-method.com/tasks/303

algo-303

import Foundation

let n = Int(readLine()!)!
let aa = readLine()!.split(separator:" ").map { Int(String($0))! }

var nodes: [Int?] = .init(repeating: nil, count: n)

func dp(_ i: Int) -> Int {
    if let r = nodes[i] { return r }
    if i == 0 { return 0 }
    if i == 1 { return aa[1] }
    let r = min(dp(i - 1) + aa[i], dp(i - 2) + aa[i - 0] * 2)
    nodes[i] = r
    return r
}

print(dp(n - 1))

algo-304

import Foundation

let n = Int(readLine()!)!

var dp: [Int] = .init(repeating: 0, count: n+1)
dp[0] = 1
dp[1] = 1

for i in 2 ..< n+1 {
    dp[i] = dp[i - 2] + dp[i - 1]
}

print(dp[n])

algo-305

import Foundation

let n = Int(readLine()!)!

var dp: [Int] = .init(repeating: 0, count: n+1)
dp[0] = 1
dp[1] = 1
dp[2] = 2

for i in 3 ..< n+1 {
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
}

print(dp[n])

algo-306

import Foundation

func readInt1() -> Int {
    Int(readLine()!)!
}

func readIntN(line: Int = #line, file: String = #file) -> [Int] {
    readLine()!.split(separator: " ").map { Int(String($0))! }
}

let nm = readLine()!.split(separator:" ").map{Int(String($0))!}
let (n, m) = (nm[0], nm[1])
let aa = readLine()!.split(separator:" ").map { Int(String($0))! }

var dp: [Int] = .init(repeating: 0, count: n)
dp[0] = 0
dp[1] = aa[1]
for i in 2 ..< n {
    var c: [Int] = []
    for j in 1..<m {
        if i - j < 0 { continue }
        c.append(dp[i - j] + aa[i] * j)
    }
    dp[i] = c.min()!
}

print(dp[n - 1])