题目描述
给定由n个整数A[0],A[1],A[2],A[3],….A[n-1]组成的数组A。你想输出一个二维的n*n的数组B，
其中数组B[i,j] (i
第一种解法思路
For i =0,1,2,...n-2
For j = i+1,i+2,....n-1
将A[i]->A[j]的累加和赋值给B[i,j]由于要满足j>i，这样来说二维矩阵的对角线是不需要进行计算的，而且最后一行一直是j>=i也不用计算，所以第一层for循环是[0~n-2]
外层循环运算次数N级别，内层用高斯求和N^2级别，所以时间复杂度是O(N^3)
第二种解法
for i = 0,1,2...n-2
b[i][i+1] = a[i] + a[i+1]
for i = 0,1,2,3...n-2
for j = i+2,i+3,....n-1
b[i][j] = b[i][j] + a[j]思路：
b[0][1] = a[0] + a[1]
b[0][2] = a[0] + a[1] + a[2] = b[0][1] + a[2]
b[0][3] = a[0] + a[1] + a[2] + a[3] = b[0][2] + a[3]
。。。
b矩阵的b[i][j] = b[i][j-1] + a[j]，这样中间的计算结果能够被利用，而且减少了重复的计算。
分析算法，第一次for循环O(n），第二次两个for循环O(n^2)，所以整个算法的时间复杂度是O(n^2)
程序代码
"""
给定由n个整数A[1],A[2],A[3],....A[n]组成的数组A。你想输出一个二维的n*n的数组B，
其中数组B[i,j](i<j)包含数组项A[i]~A[j]的和,即和A[i]+A[i+1].....A[j](只要i>=j,
数组的项B[i,j]的值不用指定，因此不管这些值的输出.)
"""
def fun(A):
n = len(A)
B = [[0 for i in range(0,n)] for j in range(0,n)]
for i in range(0,n-1):
for j in range(i+1,n):
sum = (A[i]+A[j])*(j-i+1)//2
B[i][j] = sum
return B
def fun2(A):
n = len(A)
B = [[0 for i in range(0,n)] for j in range(0,n)]
for i in range(0,n-1):
B[i][i+1] = A[i] + A[i+1]
for i in range(0,n-1):
for j in range(i+2,n):
B[i][j] = B[i][j-1] + A[j]
return B
def test():
A = [1,2,3,4,5]
result = fun(A)
for i in range(len(A)):
print(result[i])
def test2():
A = [1,2,3,4,5]
result = fun2(A)
for i in range(len(A)):
print(result[i])
if __name__ == '__main__':
test()
print("=====")
test2()程序有待验证，如有错误谢谢指出