Swift solution - Dynamical Programming


  • 0
    class Solution {
        func getMoneyAmount(_ n: Int) -> Int {
            if n < 2 {
                return 0
            }
            
            var dp = [[Int]](repeatElement([Int](repeatElement(0, count: n + 1)), count: n + 1))
            
            for j in 2...n {
                for i in stride(from: j - 1, to: 0, by: -1) {
                    var globalMin = Int.max
                    for k in (i + 1)..<j {
                        let localMax = k + max(dp[i][k - 1], dp[k + 1][j])
                        globalMin = min(globalMin, localMax)
                    }
                    dp[i][j] = i + 1 == j ? i : globalMin
                }
            }
            
            return dp[1][n]
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.