Minimum Cost to Merge Stones

// Accepted solution for LeetCode #1000: Minimum Cost to Merge Stones
class Solution {
    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        if ((n - 1) % (K - 1) != 0) {
            return -1;
        }
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + stones[i - 1];
        }
        int[][][] f = new int[n + 1][n + 1][K + 1];
        final int inf = 1 << 20;
        for (int[][] g : f) {
            for (int[] e : g) {
                Arrays.fill(e, inf);
            }
        }
        for (int i = 1; i <= n; ++i) {
            f[i][i][1] = 0;
        }
        for (int l = 2; l <= n; ++l) {
            for (int i = 1; i + l - 1 <= n; ++i) {
                int j = i + l - 1;
                for (int k = 1; k <= K; ++k) {
                    for (int h = i; h < j; ++h) {
                        f[i][j][k] = Math.min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1]);
                    }
                }
                f[i][j][1] = f[i][j][K] + s[j] - s[i - 1];
            }
        }
        return f[1][n][1];
    }
}

// Accepted solution for LeetCode #1000: Minimum Cost to Merge Stones
func mergeStones(stones []int, K int) int {
	n := len(stones)
	if (n-1)%(K-1) != 0 {
		return -1
	}
	s := make([]int, n+1)
	for i, x := range stones {
		s[i+1] = s[i] + x
	}
	f := make([][][]int, n+1)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, K+1)
			for k := range f[i][j] {
				f[i][j][k] = 1 << 20
			}
		}
	}
	for i := 1; i <= n; i++ {
		f[i][i][1] = 0
	}
	for l := 2; l <= n; l++ {
		for i := 1; i <= n-l+1; i++ {
			j := i + l - 1
			for k := 2; k <= K; k++ {
				for h := i; h < j; h++ {
					f[i][j][k] = min(f[i][j][k], f[i][h][k-1]+f[h+1][j][1])
				}
			}
			f[i][j][1] = f[i][j][K] + s[j] - s[i-1]
		}
	}
	return f[1][n][1]
}

# Accepted solution for LeetCode #1000: Minimum Cost to Merge Stones
class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n - 1) % (K - 1):
            return -1
        s = list(accumulate(stones, initial=0))
        f = [[[inf] * (K + 1) for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            f[i][i][1] = 0
        for l in range(2, n + 1):
            for i in range(1, n - l + 2):
                j = i + l - 1
                for k in range(1, K + 1):
                    for h in range(i, j):
                        f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])
                f[i][j][1] = f[i][j][K] + s[j] - s[i - 1]
        return f[1][n][1]

// Accepted solution for LeetCode #1000: Minimum Cost to Merge Stones
/**
 * [1000] Minimum Cost to Merge Stones
 *
 * There are n piles of stones arranged in a row. The i^th pile has stones[i] stones.
 * A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.
 * Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.
 *  
 * Example 1:
 *
 * Input: stones = [3,2,4,1], k = 2
 * Output: 20
 * Explanation: We start with [3, 2, 4, 1].
 * We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
 * We merge [4, 1] for a cost of 5, and we are left with [5, 5].
 * We merge [5, 5] for a cost of 10, and we are left with [10].
 * The total cost was 20, and this is the minimum possible.
 *
 * Example 2:
 *
 * Input: stones = [3,2,4,1], k = 3
 * Output: -1
 * Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.
 *
 * Example 3:
 *
 * Input: stones = [3,5,1,2,6], k = 3
 * Output: 25
 * Explanation: We start with [3, 5, 1, 2, 6].
 * We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
 * We merge [3, 8, 6] for a cost of 17, and we are left with [17].
 * The total cost was 25, and this is the minimum possible.
 *
 *  
 * Constraints:
 *
 * 	n == stones.length
 * 	1 <= n <= 30
 * 	1 <= stones[i] <= 100
 * 	2 <= k <= 30
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/minimum-cost-to-merge-stones/
// discuss: https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    // Credit: https://leetcode.com/problems/minimum-cost-to-merge-stones/solutions/850829/0ms-rust-beats-100/
    pub fn merge_stones(stones: Vec<i32>, k: i32) -> i32 {
        let k = k as usize;
        if (stones.len() - 1) % (k - 1) != 0 {
            return -1;
        }
        let mut dp = vec![vec![0; stones.len()]; stones.len()];
        let sum = {
            let mut sum = Vec::with_capacity(stones.len() + 1);
            sum.push(0);
            let mut cur = 0;
            sum.extend(stones.iter().map(|n| {
                cur = cur + n;
                cur.clone()
            }));
            sum
        };
        for len in (k - 1)..stones.len() {
            for i in 0..(stones.len() - len) {
                let j = i + len;
                dp[i][j] = (i..j)
                    .step_by(k - 1)
                    .map(|l| dp[i][l] + dp[l + 1][j])
                    .min()
                    .unwrap();
                if (j - i) % (k - 1) == 0 {
                    dp[i][j] += sum[j + 1] - sum[i];
                }
            }
        }
        dp[0][stones.len() - 1]
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1000_example_1() {
        let stones = vec![3, 2, 4, 1];
        let k = 2;
        let result = 20;

        assert_eq!(Solution::merge_stones(stones, k), result);
    }

    #[test]
    fn test_1000_example_2() {
        let stones = vec![3, 2, 4, 1];
        let k = 3;
        let result = -1;

        assert_eq!(Solution::merge_stones(stones, k), result);
    }

    #[test]
    fn test_1000_example_3() {
        let stones = vec![3, 5, 1, 2, 6];
        let k = 3;
        let result = 25;

        assert_eq!(Solution::merge_stones(stones, k), result);
    }
}

// Accepted solution for LeetCode #1000: Minimum Cost to Merge Stones
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1000: Minimum Cost to Merge Stones
// class Solution {
//     public int mergeStones(int[] stones, int K) {
//         int n = stones.length;
//         if ((n - 1) % (K - 1) != 0) {
//             return -1;
//         }
//         int[] s = new int[n + 1];
//         for (int i = 1; i <= n; ++i) {
//             s[i] = s[i - 1] + stones[i - 1];
//         }
//         int[][][] f = new int[n + 1][n + 1][K + 1];
//         final int inf = 1 << 20;
//         for (int[][] g : f) {
//             for (int[] e : g) {
//                 Arrays.fill(e, inf);
//             }
//         }
//         for (int i = 1; i <= n; ++i) {
//             f[i][i][1] = 0;
//         }
//         for (int l = 2; l <= n; ++l) {
//             for (int i = 1; i + l - 1 <= n; ++i) {
//                 int j = i + l - 1;
//                 for (int k = 1; k <= K; ++k) {
//                     for (int h = i; h < j; ++h) {
//                         f[i][j][k] = Math.min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1]);
//                     }
//                 }
//                 f[i][j][1] = f[i][j][K] + s[j] - s[i - 1];
//             }
//         }
//         return f[1][n][1];
//     }
// }