ต้นทุนต่ำสุดในการรวมก้อนหินใน C++

คำอธิบายปัญหา

มีก้อนหิน N ก้อนเรียงติดกัน ก้อนที่ i มี stones[i] หิน การรวม K ก้อนติดกันเป็น 1 ก้อน มีค่าใช้จ่ายเท่ากับผลรวมหินใน K ก้อนนั้น หาต้นทุนต่ำสุดในการรวมทั้งหมดเป็น 1 ก้อน หากไม่ได้คืน -1

ตัวอย่าง

stones = [3,2,4,1], K = 2 → Output: 20
ขั้นตอน: [3,2,4,1] → merge [3,2] cost 5 → [5,4,1] → merge [4,1] cost 5 → [5,5] → merge [5,5] cost 10 → [10] รวม = 20

เงื่อนไขความเป็นไปได้

ต้องมี (n-1) % (k-1) == 0 มิฉะนั้นคืน -1

แนวทางแก้ปัญหา: Dynamic Programming

State: dp[i][j] = ต้นทุนต่ำสุดรวมก้อน i..j ให้กลายเป็นจำนวนก้อนที่ถูกต้อง (อาจยังไม่ใช่ 1 ก้อน)

Transition:

• ลองแบ่งที่ mid โดยข้ามทีละ k-1: dp[i][j] = min(dp[i][mid] + dp[mid+1][j])
• ถ้า (j-i) % (k-1) == 0 หมายความว่าสามารถรวมเป็น 1 ก้อนได้ → บวก prefix[j+1]-prefix[i]

Prefix Sum

prefix[0] = 0
for i=1..n: prefix[i] = prefix[i-1] + stones[i-1]
// ผลรวม i..j = prefix[j+1] - prefix[i]

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        int n = stones.size();
        if((n-1) % (k-1) != 0) return -1;
        
        vector<int> prefix(n+1);
        for(int i=1; i<=n; i++) prefix[i] = prefix[i-1] + stones[i-1];
        
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for(int len=k; len<=n; len++) {
            for(int i=0, j=len-1; j