用双向动态规划，避免连续的动态规划被中断

题目链接-来源：力扣（LeetCode）

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

示例:

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

思路：

由于不能用除法（实际上，给出的数组元素中会出现 0，如果我们使用除法的话也需要考虑很多额外判断），我们考虑用动态规划实现，避免每次暴力计算乘积。
动态规划的阻碍在于，每次计算乘积 B[i] 的时候我们需要忽略 A[i]，将其视为 1 作积，相当于一段连乘被中断于 A[i] 处。但我们注意到， A[0] 到 A[i - 1] 仍然是连乘，我们记 f(0,i - 1) 为 A[0] 到 A[i - 1] 的连乘，则有
f(0, i - 1) = f(0, i - 2) * A[i - 1] 。
同理，对于 A[i] 右侧元素，有
f(i + 1, n - 1) = f(i + 2, n - 1) * A[i + 1]。
我们只要进行两轮动态规划，将 f(0, i - i) 的结果暂存进 B[i]，在第二轮时再将 f(i + 1, n - 1) 的结果乘进 B[i]，即可得出最终的结果。

时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] constructArr(int[] a) {
        int len = a.length;
        int[] res = new int[len];
        int prod = 1;
        for (int i = len - 1; i >= 0; i--) {
            res[i] = prod;
            prod *= a[i];
        }
        prod = 1;
        for (int i = 0; i <= len - 1; i++) {
            res[i] *= prod;
            prod *= a[i];
        }
        
        return res;
    }
}