剑指offer：构建乘积数组

题目描述
给定一个数组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];）

方法一:直接计算

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        lena=len(A)
        B=[]
        for i in range(lena):
            temp=A[i]
            new=1
            A[i]=1
            for j in range(lena):
                new*=A[j]
            B.append(new)
            A[i]=temp
        return B

方法二：动态规划
参考：牛客网讨论

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        lena=len(A)
        B=[0 for i in A]
        right=[0 for i in A]
        left=[0 for i in A]
        right[lena-1]=1
        left[0]=1
        i=lena-2
        while i>=0:
            right[i]=right[i+1]*A[i+1]
            i-=1
        i=1
        while i<lena:
            left[i]=left[i-1]*A[i-1]
            i+=1
        for i in range(lena):
            B[i]=left[i]*right[i]
        return B