2052. Minimum Cost to Separate Sentence Into Rows

class Solution:
    def minimumCost(self, sentence: str, k: int) -> int:
        @cache
        def dfs(i):
            if s[-1] - s[i] + n - i - 1 <= k:
                return 0
            res, j = inf, i + 1
            while j < n and (t := s[j] - s[i] + j - i - 1) <= k:
                res = min(res, (k - t) ** 2 + dfs(j))
                j += 1
            return res

        t = [len(w) for w in sentence.split()]
        n = len(t)
        s = list(accumulate(t, initial=0))
        return dfs(0)