面试题66：构建乘积数组

题目：
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

思路：
这道题需要用到动态规划的思路，具体见剑指offer，在结果上优化，只需要一个临时数组B = B[i-1]*A[i-1]，temp保存A[i]之后的乘积结果，倒叙开始求解B乘以B[i]中的元素得到最终的B。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        #新建一个临时数组B
        B = [1]*len(A)
        #赋值B
        for i in range(1,len(A)):
            B[i] = B[i-1]*A[i-1]
        #逆序构建A
        temp = 1
        for j in range(len(A)-2,-1,-1): #最后一个已经计算完毕
            temp *=A[j+1]
            B[j] *= temp
        return B

提交结果：