Day 62 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/optimal-binary-search-tree2214/1

Optimal binary search tree

Difficulty: Hard Accuracy: 50.02%

You are given a set of distinct keys in sorted order, which is represent by keys[]. Each key ki represents a data record that is accessed during a seach operation. For all the keys, you are also given a frequency array freq[], which denotes how many times key ki is searched for.
The cost of accessing a key in a binary search tree is calculated by multiplying its access frequency by the level at which it appears in the tree. Therefore different arrangements of keys in the BST gives different total search costs.
Your task is to calculate the minimum total search cost required to construct a binary search tree containing all the keys.
Note: Consider the root of the BST is at level 1.

Examples:
Input: keys[] = [10, 12], freq[] = [34, 50]
Output: 118

Explaination: There can be following two possible BSTs

The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118
Input: keys[] = [10, 12, 20], freq[] = [34, 8, 50]
Output: 142

Explaination: There can be many possible BSTs

Among all possible BSTs,
cost of the 5th BST is minimum.

Cost of this BST is 1*50 + 2*34 + 3*8 = 142
Constraints:
1 ≤ keys.size() = freq.size() ≤ 100
1 ≤ keys[i], freq[i] ≤ 104

Solution:
class Solution:
def minCost(self, keys, freq):
n = len(keys)
dp = [[0]n for _ in range(n)]
ps = [0](n+1)
for i in range(n):
ps[i+1] = ps[i] + freq[i]
for i in range(n):
dp[i][i] = freq[i]
for L in range(2, n+1):
for i in range(n-L+1):
j = i+L-1
total = ps[j+1] - ps[i]
dp[i][j] = float('inf')
for r in range(i, j+1):
left = dp[i][r-1] if r>i else 0
right = dp[r+1][j] if r<j else 0
dp[i][j] = min(dp[i][j], left + right + total)
return dp[0][n-1]