Lua石子合并：相邻合并的区间代价

local function prefix(stones)
    local pre = {0}
    for i, v in ipairs(stones) do
        pre[i + 1] = pre[i] + v
    end
    return pre
end

local function mergeCost(stones)
    local n, pre = #stones, prefix(stones)
    local dp = {}
    for i = 1, n do
        dp[i] = {}
        dp[i][i] = 0
    end
    for length = 2, n do
        for i = 1, n - length + 1 do
            local j = i + length - 1
            dp[i][j] = math.huge
            for k = i, j - 1 do
                local c = dp[i][k] + dp[k + 1][j]
                    + pre[j + 1] - pre[i]
                if c < dp[i][j] then dp[i][j] = c end
            end
        end
    end
    return dp[1][n]
end
local p = getplayerbyname("stone01")
sendmsg(p, 1, "最少代价 " .. mergeCost({3, 6, 2, 8, 4}))