- Joined
- Nov 15, 2023
- Messages
- 4
- Reaction score
- 0
For the above question I have the python solution, but it fails in hidden test cases. (Although the code pass the non hidden test cases)
Following is my code.
Python:
def findMinimumDifficulty(n: int, k: int, a: List[int]) -> int:
# write your code here
if n==k:
return 0
memo = {}
def backtrack(i, remaining_k, accumulated_sum, consecutive_count):
if (i, remaining_k, accumulated_sum, consecutive_count) in memo:
return memo[(i, remaining_k, accumulated_sum, consecutive_count)]
if remaining_k == 0:
return accumulated_sum
elif i >= n:
return 999999
current_diff = backtrack(i + 1, remaining_k - 1, accumulated_sum + a[i] + consecutive_count, consecutive_count)
next_diff = backtrack(i + 1, remaining_k, accumulated_sum, consecutive_count + 1)
memo[(i, remaining_k, accumulated_sum, consecutive_count)] = min(current_diff, next_diff)
return memo[(i, remaining_k, accumulated_sum, consecutive_count)]
return backtrack(0, n - k, 0, 0)
Error: Time Limit Exceed.
I am also open for suggestion and new approach.
If anyone can solve it with dynamic programming, it will be very helpful.