Bob has an array of size n. He loves to play with these n numbers. Each time he plays with them, he picks up any two consecutive numbers and adds them. On adding both the numbers, it costs him k*(sum of both number). Find the minimum cost of adding all the numbers in the array.
Example 1- n=3 & k=2; Array elements are {1,2,3} Output : 18
Example 2- n=4 & k=3; Array elements are {4,5,6,7} Output : 132
why you all are downvoting the post! Its really a nice problem. Not just brute force like sort it or something like that. If you get the solution, Kindly let me know in the comments. It's definitely NOT SO EASY ONE!!!
Because of this lame title.
you should have written constraints and time limit or the time complexity of the solution required..
Isn't it just greedy? Put all in a priority queue, take 2 minimal, add them, put the sum back in the queue?
Also, it reminds me of how you encode symbols with Huffman codes — each symbol has its weight (= frequency) and you build a binary tree such as sum(char.freq * len(char.code)) is minimal. This problem can also be thought as a binary tree where you put numbers in leaves and want to minimize sum(x * depth[x])
Actually real question is different,we can only add adjacent elements, so it's n^3 range dp, if you know better solution than dp then do share.
This is my recursive approach plz tell me whether it is correct or not. https://github.com/wargraver/CODES/blob/master/Dynamic%20Programming/Modified_mcm.cpp
You could see similar question [link](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space)
You can compare your solution from here , only change here is * becomes + and max becomes sum. rest everything is same.
'he picks up any two numbers' — for me that's a clear indication that the numbers don't have to be adjacent. Didn't you misread the problem?
I'll think about the case when you should only add adjacent numbers
It was asked to me on telegram by someone,I have ss of that problem if u want
Is this you alt then? Otherwise why do you state that your problem was the 'real' one?
Because mostly the question is from hiring challenge now it's very small chance that question is that similar with just little change.
p.s. I Don't use alt for posting question, also you could compare our codes if u still think it's my alt our templates are very different for each code.
I just asked you because might be you could provide optimal solution than dp. Because I was stuck on that question too.