leetcode: 120. Triangle

problem

• https://leetcode.com/problems/triangle/

O(N^2) space

• N is number of rows

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {
        val rows = triangle.size
        val dp = Array(rows) { IntArray(rows) { 0 }}
        dp[0][0] = triangle[0][0]
        
        for (row in 1 until rows) {
            val cols = triangle[row].size
            for (col in 0 until cols) {
                if (col == 0) {
                    dp[row][col] = dp[row - 1][col] + triangle[row][col]
                } else if (col == cols - 1) {
                    dp[row][col] = dp[row - 1][col - 1] + triangle[row][col]
                } else {
                    dp[row][col] = minOf(dp[row - 1][col - 1], dp[row -1][col]) + triangle[row][col]
                }
            }
        }
        return dp[rows - 1].min()!!
    }
}

O(N) space - top-down

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {    
        val rows = triangle.size
        val dp = IntArray(rows) { 0 }
        val prev = IntArray(rows) { 0 }
        dp[0] = triangle[0][0]
        
        for (row in 1 until rows) {                
            val cols = triangle[row].size
            for (col in 0 until cols) {
                // store previous value
                prev[col] = dp[col]
                // calculate next value
                if (col == 0) {
                    dp[col] = prev[col] + triangle[row][col]
                } else if (col == cols - 1) {
                    dp[col] = prev[col - 1] + triangle[row][col]
                } else {
                    dp[col] = minOf(prev[col], prev[col - 1]) + triangle[row][col]
                }
            }
        }
        return dp.min()!!
    }
}

O(N) space - bottom up

class Solution {
    fun minimumTotal(triangle: List<List<Int>>): Int {    
        val rows = triangle.size
        val dp = IntArray(rows + 1) { 0 }
        // bottom-up
        for (row in (rows - 1) downTo 0) {
            val cols = triangle[row].size
            for (col in 0 until cols) {
                dp[col] = minOf(dp[col], dp[col + 1]) + triangle[row][col]
            }
        }
        return dp[0]
    }
}