백준 14494번 다이내믹이 뭐예요? (swift) [S2]

DP(다이내믹 프로그래밍)

생각회로

• n,m 배열 선언후 문제에 나와있는 대로 for문을 돈다.

주의사항

• 
• 문제의 예시는 오른쪽, 아래로만 갈 수 있는 예시이다.
• 대각선 아래도 생각해야된다..
• 가만히 있는 것도 하나의 경우이다.

import Foundation

var input = readLine()!.split(separator: " ").map{Int(String($0))!}

let n = input[0]
let m = input[1]

var dp = Array(repeating: Array(repeating: 0, count: m), count: n)

dp[0][0] = 1

for i in 1..<n{
    dp[i][0] = dp[i-1][0]
}
for i in 1..<m{
    dp[0][i] = dp[0][i-1]
}


for i in 1..<n{
    for j in 1..<m{
        dp[i][j] = (dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]) % 1_000_000_007
    }
}

print(dp[n-1][m-1])