Java O(n) DP Solution


  • 20
    public class Solution {
        public int findMinMoves(int[] machines) {
            int total = 0, target = 0, result = 0, n = machines.length;
            for (int d : machines) total += d;
            if (total == 0) return 0;
            if (total % n != 0) return -1;
            target = total / n;
            
            int[] move = new int[n];
            for (int i = 0; i < n - 1; i++) {
                if (machines[i] > target) {
                    move[i] += machines[i] - target;
                    machines[i + 1] += machines[i] - target;
                    machines[i] = target;
                    result = Math.max(result, move[i]);
                }
                else {
                    move[i + 1] = target - machines[i];
                    machines[i + 1] -= target - machines[i];
                    machines[i] = target;
                    result = Math.max(result, move[i + 1]);
                }
            }
            
            return result;
        }
    }
    

  • 1

    @shawngao Thank you for your solution! I am doubled why you call it by Dynamic Programming. This problem is difiicult for me since I find it hard to abstract to a model or algorithm I am familiar with. I will appreciate if you could explain more


  • 1
    S

    @victorzhang21503 I think he is trying to find the peak who give the most items to two side, which is equal to the maximum movement.


  • 0

    I don't think this is DP solution


  • 3
    J

    I appreciate this nice and clean code. I was first attracted by "DP" in the topic. However, it's not DP. It's more like a deduction rather than optimal substructure.

    One insight I want to add:
    You could consider this problem as a pipeline, and the bandwidth of pipeline is "1". From the leftist machine to the right, the water flows in / out. To get the balanced state, calculate how many times you need to use this pipeline.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.