2052. Minimum Cost to Separate Sentence Into Rows

You are given a string sentence containing words separated by spaces, and an integer k. Your task is to separate sentence into rows where the number of characters in each row is at most k. You may assume that sentence does not begin or end with a space, and the words in sentence are separated by a single space.

You can split sentence into rows by inserting line breaks between words in sentence. A word cannot be split between two rows. Each word must be used exactly once, and the word order cannot be rearranged. Adjacent words in a row should be separated by a single space, and rows should not begin or end with spaces.

The cost of a row with length n is (k - n)2, and the total cost is the sum of the costs for all rows except the last one.

• For example if sentence = “i love leetcode” and k = 12:

• Separating sentence into “i”, “love”, and “leetcode” has a cost of (12 - 1)2 + (12 - 4)2 = 185.
• Separating sentence into “i love”, and “leetcode” has a cost of (12 - 6)2 = 36.
• Separating sentence into “i”, and “love leetcode” is not possible because the length of “love leetcode” is greater than k.

Return the minimum possible total cost of separating sentence into rows.

class Solution {
    long long dp[5050];
    long long helper(string& s, int k, int p) {
        if(dp[p] != -1) return dp[p];
        int n = s.length();
        if(n - k <= p) return 0;
        long long& res = dp[p] = INT_MAX;
        for(int i = p; i <= p + k; i++) {
            if(s[i] == ' ') {
                res = min(res, (k - (i - p)) * (k - (i - p)) + helper(s,k,i+1));
            }
        }
        return res;
    }
public:
    int minimumCost(string sentence, int k) {
        memset(dp,-1,sizeof dp);
        
        return helper(sentence, k, 0);
    }
};