백준 - 쉬운 계단 수 (10844)

let MOD = 1000000000
let N = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: N + 1)

// dp 테이블 초기화
for i in 1...9 {
    dp[1][i] = 1
}

// 나머지 dp 테이블 채우기
for i in stride(from: 2, through: N, by: 1) {
    dp[i][0] = dp[i - 1][1]
    dp[i][9] = dp[i - 1][8]
    for j in 1...8 {
        dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD
    }
}
print(dp[N].reduce(0) { ($0 + $1) % MOD })

N번째 자리에 높이가 0인 계단이 오는 경우는 N-1번째 계단이 1인 경우밖에 없다. (내려가는 경우)

마찬가지로 N번째 자리에서 높이가 9인 계단이 오는 경우는 N-1번째 계단이 8인 경우밖에 없다. (올라가는 경우)

나머지는 내려오는 경우와 올라오는 경우 둘 다 가능하다.