World's most popular travel blog for travel bloggers.

[Solved]: Why is this problem listed as "Dynamic Programming"

, , No Comments
Problem Detail: 

I found a problem in the dynamic programming section of hackerrank but its not clear why dynamic programming should be used to solve it. The problem is as follows:

Nikita just came up with a new array game. The rules are as follows: Initially, there is an array, , containing integers. In each move, Nikita must partition the array into non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets point; otherwise, the game ends. After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array . Nikita loves this game and wants your help getting the best score possible. Given , can you find and print the maximum number of points she can score?

In going over the algorithm that would be used to solve the problem, it seemed evident to me that you could simply write a recursive function where each recursive call would be made iff the sums of the elements in both halves of the array are equal. Otherwise, the game (the algorithm) ends. Since you would, in the worst case (running time wise), be dividing the array log(n) times where n is the array length, you would get a running time of O(logn).

The only thing that I could see dynamic programming helping with here may be the recalculation of the sums which I guess could be avoided by calculating the sums from the bottom up but I'm not really seeing an optimal substructure here. Also, you would be increasing the space complexity seemingly unnecessarily.

So why/how is dynamic programming being used here?

Asked By : loremIpsum1771

Answered By : Yuval Filmus

How do you choose which partition is best (there could be several partitions if you allow negative numbers or zeroes), and which side of the partition to choose? You have to examine all partitions and both sides of each partition, and then choose the best one. Naively, the complexity of this algorithm is exponential. With dynamic programming you can find the solution in polynomial time – I'll let you figure out how.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback