'''
题目描述
给定一个数组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]。不能使用除法。
'''
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
B=[1]*len(A)
for i in range(len(B)):
for j in range(i):
B[i]*=A[j]
for k in range(i+1,len(A)):
B[i]*=A[k]
return B
'''
计算数组B中每个元素的数值的时候将会出现很多重叠的子问题
使用动态规划的思想，计算出数组B中的第i个元素相当于计算出下面的二维数组第i行的所有元素的乘积
假设当前的数组A中有5个元素
1 A[1] A[2] A[3] A[4]
A[0] 1 A[2] A[3] A[4]
A[0] A[1] 1 A[3] A[4]
A[0] A[1] A[2] 1 A[4]
A[0] A[1] A[2] A[3] 1
把二维数组中每一行的乘积分成两个部分求解：左边部分和右边部分
左边部分是下三角矩阵，直接使用求解斐波那契数列的思路即可
右边部分是上三角矩阵，使用从下向上的求解思路求解乘积即可
'''
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
line_left=[1 for _ in range(len(A))]
line_right = [1 for _ in range(len(A))]
B=[1 for _ in range(len(A))]
# mid=[[1 for _ in range(len(A))] for i in range(len(A))]
for i in range(1,len(A)):
line_left[i]=A[i-1]*line_left[i-1]
line_right[len(A)-i-1]=A[len(A)-i]*line_right[len(A)-i]
for k in range(len(A)):
B[k]=line_right[k]*line_left[k]
return B | 
转播
