小红的星尘收集

题目分析

小红在太空中发现一排星尘簇，每个星尘簇有一个能量值。收集第 个位置的星尘时，相邻的第 和第 个星尘会消散，无法再被收集。求能获得的最大能量总和。

这是经典的打家劫舍问题：从一排数中选取若干个，要求任意两个被选中的数不相邻，使得总和最大。

思路

动态规划

定义 为考虑前 个星尘时能获得的最大能量。对于第 个星尘，有两种决策：

  • 不收集：最大能量等于 。
  • 收集：获得 的能量，但第 个不能选，所以最大能量等于 。

取两者较大值：

$$

初始条件：，（虚拟边界）。

由于 只依赖前两个状态，可以用两个变量滚动优化，空间复杂度降为 。

示例推演

输入 2 7 10 3 2：

prev2 prev1 说明
0 2 0 2 初始
1 7 2 7
2 10 7 12
3 3 12 12
4 2 12 14

答案为 ，对应选取位置 （能量 ）。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<long long> a;
    long long x;
    while(cin >> x) a.push_back(x);

    int n = a.size();
    if(n == 0){
        cout << 0 << endl;
        return 0;
    }
    if(n == 1){
        cout << a[0] << endl;
        return 0;
    }

    long long prev2 = 0, prev1 = a[0];
    for(int i = 1; i < n; i++){
        long long cur = max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    cout << prev1 << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine().trim();
        if (line.isEmpty()) {
            System.out.println(0);
            return;
        }
        String[] parts = line.split("\\s+");
        int n = parts.length;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(parts[i]);
        }
        if (n == 1) {
            System.out.println(a[0]);
            return;
        }
        long prev2 = 0, prev1 = a[0];
        for (int i = 1; i < n; i++) {
            long cur = Math.max(prev1, prev2 + a[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        System.out.println(prev1);
    }
}

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    a = list(map(int, data))
    n = len(a)
    if n == 1:
        print(a[0])
        return
    prev2, prev1 = 0, a[0]
    for i in range(1, n):
        prev2, prev1 = prev1, max(prev1, prev2 + a[i])
    print(prev1)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const parts = line.trim().split(/\s+/);
    if (parts.length === 0 || (parts.length === 1 && parts[0] === '')) {
        console.log(0);
        return;
    }
    const a = parts.map(Number);
    const n = a.length;
    if (n === 1) {
        console.log(a[0]);
        return;
    }
    let prev2 = 0, prev1 = a[0];
    for (let i = 1; i < n; i++) {
        const cur = Math.max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    console.log(prev1);
});

复杂度分析

  • 时间复杂度：，其中 为星尘数量，只需遍历一次数组。
  • 空间复杂度：（不计输入存储），仅使用两个滚动变量。