【动态规划3】前缀和问题

题面描述：

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，要求你计算并输出每个前缀的和，即求出：

其中， $1 \leq i \leq n$，即对于序列的每个前缀，输出其对应的和。

思路解析：

1. 问题理解： 给定一个序列 $a_1, a_2, \dots, a_n$，需要计算并输出前 $i$ 个元素的和 $S_i$，其中 $S_i$ 是从第 1 个元素到第 $i$ 个元素的累加和。

2. 前缀和： 对于每个 $i$ 的前缀和，我们可以通过累加方式来计算。例如，$S_1 = a_1$，$S_2 = a_1 + a_2$，依此类推。显然，当前的前缀和 $S_i$ 可以通过前一个前缀和 $S_{i-1}$ 加上当前元素 $a_i$ 得到。

3. 动态规划： 为了高效地计算前缀和，我们可以使用一个动态规划数组 $dp$，其中 $dp[i]$ 表示从第 1 个元素到第 $i$ 个元素的前缀和。初始状态下，设置 $dp[0] = 0$（表示空序列的和为 0），然后根据递推关系：

   $$dp[i] = dp[i-1] + a[i-1]$$

   即：当前前缀和等于前一个前缀和加上当前元素。

代码

cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 读取输入
    int n;
    cin >> n; // 输入序列的长度
    vector<int> a(n); // 存储整数序列
    for (int i = 0; i < n; ++i) {
        cin >> a[i]; // 输入序列中的每个整数
    }

    // 动态规划数组 dp，dp[i] 表示前缀和 S_i
    vector<int> dp(n + 1, 0); // 初始化 dp 数组，dp[0] = 0

    // 根据动态规划的状态转移公式计算前缀和
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + a[i - 1]; // dp[i] = dp[i-1] + a[i-1]
        cout << dp[i] << endl; // 输出前缀和
    }

    return 0;
}

python

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])  # 输出当前的前缀和

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取输入的整数n，表示数组的长度
        int[] a = new int[n];  // 读取n个整数，存储在数组a中

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int[] dp = new int[n + 1];  // 初始化前缀和数组dp，长度为n+1，dp[0]设为0

        // 计算前缀和
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + a[i - 1];  // 当前前缀和等于前一个前缀和加上当前元素
            System.out.println(dp[i]);  // 输出当前的前缀和
        }
    }
}

4题目描述：

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，要求你计算并输出每个前缀的和，即求出：

其中， $1 \leq i \leq n$，即对于序列的每个前缀，输出其对应的和。

输入格式：

• 第一行输入一个整数 $n$（ $1 \leq n \leq 10^5$ ），表示序列的长度。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（ $1 \leq a_i \leq 10^4$ ），表示给定的整数序列。

输出格式：

• 输出 $n$ 行，每行输出一个整数 $S_i$，表示序列的第 $i$ 个前缀的和。

示例

输入：

5
1 2 3 4 5

输出：

1
3
6
10
15