计算前缀和后缀和背后的直觉

Question

我正在解决一个LeetCode question：将所有球移动到每个盒子的最少操作数。

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball. In one operation, you can move one ball from a box to an adjacent box. Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box. For input boxes = "001011", the output is: [11,8,5,4,3,4].

在 O(n^2) 中完成它是微不足道的。我只能这样解决。我试图理解 this O(n) 解决方案，但遇到困难：

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();

        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[n];

        int count = boxes.charAt(0) - '0';
        for(int i = 1 ; i < n ; i++){
            left[i] = left[i - 1] + count;
            count += boxes.charAt(i) - '0';
            // System.out.println("i: "+i+" left[i]: "+left[i]+" left[i-1] : "+left[i-1]+" count: " + count);
        }

        count = boxes.charAt(n - 1) - '0';
        for(int i = n - 2 ; i >=0 ; i--){
            right[i] = right[i + 1] + count;
            count += boxes.charAt(i) - '0';
            // System.out.println("i: "+i+" right[i]: "+right[i]+" right[i+1] : "+right[i+1]+" count: " + count);
        }
        
        for(int i = 0 ; i < n ; i++) {
            ans[i] = left[i] + right[i];
        }

        return ans;
    }
}

谁能详细说明背后的逻辑：

left[i] = left[i - 1] + count;
count += boxes.charAt(i) - '0';

我知道每当我们遇到球时我们都会递增 count，但是 left[i] = left[i - 1] + count; 如何帮助我们计算到目前为止将左侧所有球移动到 [=15] 所需的操作次数=]（反之亦然 right）？

谢谢！

Answer 1

将 left[i] 视为将所有球从 0 开始移动到第 i 个索引的成本。

所以，

left[i] = 
  left[i - 1]  (cost to move all 1's to (i - 1) the index) 
  + count      (this is the total number of 1's which will all need to be moved to the ith index so, its cost is count)

Answer 2

This comment from @dunkypie 帮助：

"I finally build the intuition for the problem using DP. Here is goes. When we say calculating the number of operations for moving all the balls to the left of a box to that bax, say we are at the i th position(or box). This consists of two parts, first dp[i - 1] will give us the number of operations to move all the balls so far till (i - 1) th position and now we have all the balls till the (i - 1) th position in the (i - 1) th position(or box). Then the next part involves moving all those balls in (i - 1) th position to the i th position. Also note the cost of moving a single ball by 1 position is 1. So the recurrence relation becomes:

dp[i] = dp[i - 1] + (1 * balls) where 1 here is the cost of moving a single ball."

计算前缀和后缀和背后的直觉

Intuition behind calculating the prefix and suffix sums

java

algorithm

prefix-sum