Python: DP
The codes are similar to other posts but I think it is better to give some clarification in terms of DP. Let\'s first think about the subproblem where we need t
The codes are similar to other posts but I think it is better to give some clarification in terms of DP. Let\'s first think about the subproblem where we need to obtain the minimum number of operations to move all LEFT balls to each Box (i.e., those balls on the left of each box). It is quite clear this is a DP problem. Denote the solution for box i as cost_i. Then we can write down the DP equation: cost_i = cost_{i-1} + the number of balls on the left of box i. This gives us the first half of the code. Similarly, we can consider the subproblem of moving all RIGHT balls to each box, which is the second half.\n\n```\nclass Solution(object):\n    def minOperations(self, boxes):\n        """\n        :type boxes: str\n        :rtype: List[int]\n        """\n        cost = [0]*len(boxes)\n        #first consider those balls that are moved from left to right\n        #cost[i] = cost[i-1] + # of balls on the left of ith box\n        #num_ball indicates number of balls on the left\n        num_ball, cost_update = 0,0\n        for i in range(len(boxes)):\n            cost[i] += cost_update\n            #update the number of balls on the left of box i+1\n            num_ball += int(boxes[i])\n            #update cost for box i+1\n            cost_update += num_ball\n        #consider those balls that are moved from right to left\n        num_ball, cost_update = 0,0\n        for i in reversed(range(len(boxes))):\n            cost[i] += cost_update\n            #update the number of balls on the right of box i-1\n            num_ball += int(boxes[i])\n            #update cost for box i-1\n            cost_update += num_ball\n            \n        return cost\n```
[]