题目描述:
给定一个长度为 n 的整数序列 a1,a2,…,an,要求你计算并输出每个前缀的和,即求出:
Si=a1+a2+⋯+ai其中, 1≤i≤n,即对于序列的每个前缀,输出其对应的和。
输入格式:
输出格式:
输入:
5
1 2 3 4 5
输出:
1
3
6
10
15
给定一个长度为 n 的整数序列 a1,a2,…,an,要求你计算并输出每个前缀的和,即求出:
Si=a1+a2+⋯+ai其中, 1≤i≤n,即对于序列的每个前缀,输出其对应的和。
问题理解: 给定一个序列 a1,a2,…,an,需要计算并输出前 i 个元素的和 Si,其中 Si 是从第 1 个元素到第 i 个元素的累加和。
前缀和: 对于每个 i 的前缀和,我们可以通过累加方式来计算。例如,S1=a1,S2=a1+a2,依此类推。显然,当前的前缀和 Si 可以通过前一个前缀和 Si−1 加上当前元素 ai 得到。
动态规划: 为了高效地计算前缀和,我们可以使用一个动态规划数组 dp,其中 dp[i] 表示从第 1 个元素到第 i 个元素的前缀和。初始状态下,设置 dp[0]=0(表示空序列的和为 0),然后根据递推关系:
dp[i]=dp[i−1]+a[i−1]即:当前前缀和等于前一个前缀和加上当前元素。
n = int(input()) # 读取输入的整数n,表示数组的长度
a = list(map(int, input().split())) # 读取n个整数,存储在列表a中
dp = [0] * (n + 1) # 初始化前缀和数组dp,长度为n+1,dp[0]设为0
# 计算前缀和
for i in range(1, n + 1):
dp[i] = dp[i - 1] + a[i - 1] # 当前前缀和等于前一个前缀和加上当前元素
print(dp[i]) # 输出当前的前缀和