Crush Consecutive Numbers - Amazon Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums, int k) {
    int n = nums.size();
    if ((n - 1) % (k - 1) != 0) return -1;

    vector<int> suff(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        suff[i] = nums[i] + suff[i + 1];
    }

    vector<vector<int>> dp(n, vector<int>(n));
    for (int sz = k; sz <= n; sz++) {
        for (int l = 0, r = sz - 1; r < n; l++, r++) {
            dp[l][r] = INT_MAX;
            // merge [l, i] into one pile, and the rest as much as possible
            for (int i = l; i < r; i += k - 1) {
                dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r]);
            }

            // after doing the above split, the interval [l, r] will be reduced to a size <= k
            // if it's reduced to k, we reduce it again to 1 by adding the final cost
            if ((r - l) % (k - 1) == 0) {
                dp[l][r] += suff[l] - suff[r + 1];
            }
        }
    }

    return dp[0][n - 1];
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums, k):
        dp = [[None] * len(nums) for _ in range(len(nums))]

        def find(i, j):
            if i == j:
                return 0
            if k != 2 and (j - i + 1) % (k - 1) != 1:
                return math.inf
            if dp[i][j] is None:
                ans = sum(nums[i : j + 1])
                min_cost = math.inf
                for split in combinations(range(i + 1, j + 1), k - 1):
                    split = list(split) + [j + 1]
                    its_cost = find(i, split[0] - 1)
                    for ind in range(len(split) - 1):
                        its_cost += find(split[ind], split[ind + 1] - 1)
                    min_cost = min(min_cost, its_cost)
                dp[i][j] = ans + min_cost
            return dp[i][j]

        return find(0, len(nums) - 1) if find(0, len(nums) - 1) != math.inf else -1