题解 | #小红的地砖#

题目链接

题目描述

小红正在进行一次体能训练，场地上依次铺设了 $n$ 块地砖，按照从 $1$ 到 $n$ 依次编号。她站在第 $1$ 块地砖上，目标是走到第 $n$ 块地砖。已知走到第 $i$ 块地砖需要消耗 $a_i$ 的体力值。每一次移动，小红可以选择：

向前走 $1$ 步，即从当前地砖 $i$ 走到地砖 $i+1$ ；
向前走 $2$ 步，即从当前地砖 $i$ 走到地砖 $i+2$ 。请你帮助小红计算，从第 $1$ 块地砖走到第 $n$ 块地砖所需消耗的最小体力值。

解题思路

这是一个经典的动态规划问题。

我们定义 $dp[i]$ 为到达第 $i$ 块地砖时所消耗的最小体力值。我们的目标是求 $dp[n]$ 。

要到达第 $i$ 块地砖（当 $i > 2$ 时），只可能从以下两个位置跳过来：

从第 $i-1$ 块地砖走 $1$ 步。此时的体力消耗为 $dp[i-1] + a_i$ 。
从第 $i-2$ 块地砖走 $2$ 步。此时的体力消耗为 $dp[i-2] + a_i$ 。

为了使得到达第 $i$ 块地砖的总体力消耗最小，我们应该选择从之前两块地砖中消耗较小的那一个跳过来。由此，我们可以得到状态转移方程： $dp[i] = \min(dp[i-1], dp[i-2]) + a_i$

接下来确定初始状态（边界条件）：

$dp[1] = a_1$ ：到达第 $1$ 块地砖的消耗就是它自身的体力值。
$dp[2] = a_1 + a_2$ ：要到达第 $2$ 块地砖，必须从第 $1$ 块跳过来，所以总消耗是前两块地砖的体力值之和。

在实现时，我们注意到计算 $dp[i]$ 只需要 $dp[i-1]$ 和 $dp[i-2]$ 的值。因此，没有必要用一个数组来存储所有的 $dp$ 值，只需用两个变量滚动地记录前两项即可。这样可以将空间复杂度从 $\mathcal{O}(n)$ 优化到 $\mathcal{O}(1)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (n == 1) {
        cout << a[0] << "\n";
        return 0;
    }

    // prev 对应 dp[i-2]，curr 对应 dp[i-1]
    long long prev = a[0];
    long long curr = a[0] + a[1];

    for (int i = 2; i < n; i++) {
        long long next = min(prev, curr) + a[i];
        prev = curr;
        curr = next;
    }

    cout << curr << "\n";

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        if (n == 1) {
            System.out.println(a[0]);
            return;
        }

        // prev 对应 dp[i-2]，curr 对应 dp[i-1]
        long prev = a[0];
        long curr = a[0] + a[1];

        for (int i = 2; i < n; i++) {
            long next = Math.min(prev, curr) + a[i];
            prev = curr;
            curr = next;
        }

        System.out.println(curr);
    }
}

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(a[0])
else:
    # prev 对应 dp[i-2]，curr 对应 dp[i-1]
    prev = a[0]
    curr = a[0] + a[1]

    for i in range(2, n):
        # 滚动更新
        prev, curr = curr, min(prev, curr) + a[i]
    
    print(curr)

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(n)$ ，我们需要一次循环遍历所有地砖。
空间复杂度： $\mathcal{O}(1)$ ，我们只使用了常数个变量来存储状态。