Day 43 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/minimum-cost-to-merge-stones/1

Minimum Cost to Merge Stones

Difficulty: Hard Accuracy: 51.38%

Given an array stones[], where the ith element represents the number of stones in the ith pile.
In one move, you can merge exactly k consecutive piles into a single pile, and the cost of this move is equal to the total number of stones in these k piles.
Determine the minimum total cost required to merge all the piles into one single pile. If it is not possible to merge all piles into one according to the given rules, return -1.
Examples:
Input: stones[] = [1, 2, 3], k = 2
Output: 9
Explanation: Initially the array looks like [1, 2, 3].
First, we merge first 2 stones, i.e., 1 and 2, array becomes [3, 3] and cost is 1 + 2 = 3.
Then, we merge remaining stones, i.e., 3 and 3, array becomes [6] and the cost = 3 + 3 = 6.
Total cost = 3 + 6 = 9.
Input: stones[] = [1, 5, 3, 2, 4], k = 2
Output: 35
Explanation: Initially the array looks like [1, 5, 3, 2, 4].
First, we merge 1 and 5, array becomes [6, 3, 2, 4] and cost is 1 + 5 = 6.
Then, we merge 3 and 2, array becomes [6, 5, 4] and the cost = 3 + 2 = 5.
Then, we merge 5 and 4, array becomes [6, 9] and the cost = 5 + 4 = 9.
Finally, we merge 6 and 9, array becomes [15] and the cost = 6 + 9 = 15.
Total cost = 6 + 5 + 9 + 15 = 35.
Input: stones[] = [1, 5, 3, 2, 4], k = 4
Output: -1
Explanation: There is no possible way to combine the stones in piles of 4 to get 1 stone in the end.
Constraints:
1 ≤ stones.size() ≤ 30
2 ≤ k ≤ 30
1 ≤ stones[i] ≤ 100

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

    ps = [0]
    for x in stones:
        ps.append(ps[-1] + x)

    dp = [[[float('inf')] * (k + 1) for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][i][1] = 0

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for m in range(2, k + 1):
                for t in range(i, j, k - 1):
                    dp[i][j][m] = min(dp[i][j][m], dp[i][t][1] + dp[t+1][j][m-1])
            dp[i][j][1] = dp[i][j][k] + ps[j+1] - ps[i]

    return dp[0][n-1][1]