1000. Minimum Cost to Merge Stones

leetcode hard

#array#csharp#dynamic-programming#hard#heap#leetcode#math#prefix-sum

Task

Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.

Пример:

Input: stones = [3,2,4,1], k = 2

Output: 20

C# solution

matched/original

public class Solution {
    public int MergeStones(int[] stones, int k) {
        int n = stones.Length;
        if ((n - 1) % (k - 1) != 0) return -1;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }
        int[,] dp = new int[n, n];
        for (int m = k; m <= n; m++) {
            for (int i = 0; i <= n - m; i++) {
                int j = i + m - 1;
                dp[i, j] = int.MaxValue;
                for (int t = i; t < j; t += k - 1) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i, t] + dp[t + 1, j]);
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i, j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0, n - 1];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MergeStones(vector<int>& stones, int k) {
        int n = stones.size();
        if ((n - 1) % (k - 1) != 0) return -1;
        vector<int>& prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }
        int[,] dp = new int[n, n];
        for (int m = k; m <= n; m++) {
            for (int i = 0; i <= n - m; i++) {
                int j = i + m - 1;
                dp[i, j] = int.MaxValue;
                for (int t = i; t < j; t += k - 1) {
                    dp[i, j] = min(dp[i, j], dp[i, t] + dp[t + 1, j]);
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i, j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0, n - 1];
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }
        int[,] dp = new int[n, n];
        for (int m = k; m <= n; m++) {
            for (int i = 0; i <= n - m; i++) {
                int j = i + m - 1;
                dp[i, j] = int.MaxValue;
                for (int t = i; t < j; t += k - 1) {
                    dp[i, j] = Math.min(dp[i, j], dp[i, t] + dp[t + 1, j]);
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i, j] += prefix[j + 1] - prefix[i];
                }
            }
        }
        return dp[0, n - 1];
    }
}

Python solution

matched/original

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1

        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + stones[i]

        dp = [[0] * n for _ in range(n)]
        for m in range(k, n + 1):
            for i in range(n - m + 1):
                j = i + m - 1
                dp[i][j] = min(dp[i][t] + dp[t + 1][j] for t in range(i, j, k - 1))
                if (j - i) % (k - 1) == 0:
                    dp[i][j] += prefix[j + 1] - prefix[i]

        return dp[0][n - 1]

Go solution

matched/original

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }

    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }

    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for m := k; m <= n; m++ {
        for i := 0; i <= n-m; i++ {
            j := i + m - 1
            dp[i][j] = int(^uint(0) >> 1) // max int
            for t := i; t < j; t += k - 1 {
                dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j])
            }
            if (j-i)%(k-1) == 0 {
                dp[i][j] += prefix[j+1] - prefix[i]
            }
        }
    }

    return dp[0][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Проверка на возможность объединения:

Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1.

Инициализация и динамическое программирование:

Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней.

Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве.

Заполнение таблицы dp:

Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование.

Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения.

😎