题解 | #小红的地砖#

题目链接

小红的地砖

题目描述

小红要走过一个有 $n$ 块地砖的场地，地砖从 $1$ 到 $n$ 编号。她从第 $1$ 块地砖出发，目标是到达第 $n$ 块地砖。

走到第 $i$ 块地砖需要消耗 $a_i$ 的体力值。
从地砖 $i$ ，她可以移动到地砖 $i+1$ （走1步）或地砖 $i+2$ （走2步）。
题目保证 $a_1=0$ 。
总消耗是所有走过的地砖的体力值之和。

请求出从第 $1$ 块地砖走到第 $n$ 块地砖所需消耗的最小体力值。

输入:

第一行一个整数 $n$ ，表示地砖数量。
第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示每块地砖的体力消耗。

输出:

一个整数，表示最小体力值。

解题思路

这是一个经典的动态规划问题，与爬楼梯问题类似，但目标是最小化成本而不是计算路径数量。

定义状态: 我们用 $dp[i]$ 表示到达第 $i$ 块地砖时，所累积的最小体力消耗。我们的最终目标是求 $dp[n]$ 。
状态转移方程: 要到达第 $i$ 块地砖，我们只可能从第 $i-1$ 块或第 $i-2$ 块地砖转移而来。
- 如果从第 $i-1$ 块地砖走来：到达 $i-1$ 的最小成本是 $dp[i-1]$ 。踏上第 $i$ 块地砖后，总成本变为 $dp[i-1] + a_i$ 。
- 如果从第 $i-2$ 块地砖走来：到达 $i-2$ 的最小成本是 $dp[i-2]$ 。踏上第 $i$ 块地砖后，总成本变为 $dp[i-2] + a_i$ 。
为了使得到达第 $i$ 块地砖的总成本最小，我们必须选择两者中成本更小的那个来源。因此，状态转移方程为： $dp[i] = \min(dp[i-1], dp[i-2]) + a_i$ （其中 $a_i$ 是走到第 $i$ 块地砖的消耗）。
确定边界条件 (Base Cases):
- 对于第 1 块地砖 ( $i=1$ )：我们从这里出发，最小成本就是 $a_1$ 。根据题意， $a_1=0$ ，所以 $dp[1] = 0$ 。
- 对于第 2 块地砖 ( $i=2$ )：只能从第 1 块地砖走 1 步到达。所以路径是 $1 \to 2$ ，总成本是 $a_1 + a_2$ 。因此 $dp[2] = dp[1] + a_2 = a_2$ 。
- 状态转移方程 $dp[i] = \min(dp[i-1], dp[i-2]) + a_i$ 适用于 $i \ge 3$ 。
空间优化: 和斐波那契数列一样，计算 $dp[i]$ 只依赖于前两个状态 $dp[i-1]$ 和 $dp[i-2]$ 。因此，我们可以使用两个变量来滚动保存这两个状态，将空间复杂度从 $\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<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

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

    long long dp_i_minus_2 = a[0]; // dp[1]
    long long dp_i_minus_1 = a[1]; // dp[2] (注意题目保证 a[0]=0)

    for (int i = 2; i < n; ++i) {
        long long dp_i = min(dp_i_minus_1, dp_i_minus_2) + a[i];
        dp_i_minus_2 = dp_i_minus_1;
        dp_i_minus_1 = dp_i;
    }

    cout << dp_i_minus_1 << endl;

    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();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

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

        long dp_i_minus_2 = a[0]; // dp[1]
        long dp_i_minus_1 = a[1]; // dp[2] (注意题目保证 a[0]=0)

        for (int i = 2; i < n; i++) {
            long dp_i = Math.min(dp_i_minus_1, dp_i_minus_2) + a[i];
            dp_i_minus_2 = dp_i_minus_1;
            dp_i_minus_1 = dp_i;
        }

        System.out.println(dp_i_minus_1);
    }
}

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

if n == 1:
    print(a[0])
else:
    # dp_i_minus_2 对应 dp[i-2] 的值, 初始化为 dp[1] 的成本
    # dp_i_minus_1 对应 dp[i-1] 的值, 初始化为 dp[2] 的成本
    dp_i_minus_2 = a[0]
    dp_i_minus_1 = a[1]

    # 从第3块地砖开始循环
    for i in range(2, n):
        # 计算到达当前地砖 i+1 的最小成本
        dp_i = min(dp_i_minus_1, dp_i_minus_2) + a[i]
        # 更新滚动变量
        dp_i_minus_2 = dp_i_minus_1
        dp_i_minus_1 = dp_i

    print(dp_i_minus_1)

算法及复杂度

算法：动态规划（滚动数组优化）
时间复杂度： $\mathcal{O}(n)$ - 我们需要遍历一次地砖数组来计算最小成本。
空间复杂度： $\mathcal{O}(n)$ - 主要用于存储输入的 $n$ 个体力值。DP计算本身的空间是 $\mathcal{O}(1)$ 。