# 28.05.2023 [1547. Minimum Cost to Cut a Stick]

28.05.2023

1547. Minimum Cost to Cut a Stick hard
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/226

Problem TLDR

Min cost of cuts c1,..,ci,..,cn of [0..n] where cut cost the length = to-from.

Intuition

We every stick from..to we can try all the cuts in that range. This result will be optimal and can be cached.

Approach

• use DFS + memo

• check for range

Complexity

• Time complexity:
  k^2, as maximum depth of DFS is k, and we loop for k.

• Space complexity:
  k^2

Code

fun minCost(n: Int, cuts: IntArray): Int {
    val cache = mutableMapOf<Pair<Int, Int>, Int>()
    fun dfs(from: Int, to: Int): Int {
        return cache.getOrPut(from to to) {
            var min = 0
            cuts.forEach {
                if (it in from + 1..to - 1) {
                    val new = to - from + dfs(from, it) + dfs(it, to)
                    if (min == 0 || new < min) min = new
                }
            }

            min
        }
    }
    return dfs(0, n)
}