Why this solution is wrong?


  • 0

    I think my idea is quite clear, but this is wrong. I can't figure out which part of my code is wrong.

    func minimumTotal(triangle: [[Int]]) -> Int {
        var myT = Array(count: triangle.count, repeatedValue: 0)
        if triangle.count == 1 {
            return triangle[0][0]
        }
        myT[0] = triangle[0][0] + triangle[1][0]
        myT[1] = triangle[0][0] + triangle[1][1]
        for row in 2..<triangle.count {
            myT[row] = triangle[row][row] + myT[row-1]
            for col in 1..<triangle[row].count-1 {
                if col != 0 && col != row {
                    myT[col] = triangle[row][col] + min(myT[col-1], myT[col])
                }
            }
            myT[0] = triangle[row][0] + myT.first!
        }
        return myT.minElement()!
    }
    

  • 0

    @zhugejunwei Well, this solution is right. But I think these two solutions are almost the same. This one is just a little shorter and more clear.

    func minimumTotal(triangle: [[Int]]) -> Int {
        var myT = triangle[triangle.count-1]
        var row = triangle.count - 2
        while row >= 0 {
            for col in 0...row {
                myT[col] = triangle[row][col] + min(myT[col],myT[col+1])
            }
            row -= 1
        }
        return myT[0]
    }
    

Log in to reply
 

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