Leetcode Problem 1000. Minimum Cost to Merge Stones

1000. Minimum Cost to Merge Stones

Leetcode Solutions

Initialize a 3D DP array dp[i][j][m] with infinity, except for dp[i][i][1] which should be 0 since merging a single pile has no cost.
Calculate the prefix sum of stones to help with range sum calculations.
Use a bottom-up approach to fill the DP array:
- For each range [i, j], try to merge it into m piles where m ranges from 1 to k.
- For m == 1, the cost is the cost to merge into k piles plus the sum of stones in [i, j].
- For m > 1, find the minimum cost by trying to split the range [i, j] into two parts at every possible split point, and add the cost of merging the left part into one pile and the right part into m-1 piles.
The answer is dp[0][n-1][1], which represents the cost to merge the whole array into one pile.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen