题目链接

小红的地砖

题目描述

小红需要从第 1 块地砖走到第 块地砖。走到第 块地砖需要消耗 的体力值。小红每次可以选择向前走一步或者向前走两步。求小红走到第 块地砖时，消耗的最小总体力值。

解题思路

这是一个经典的动态规划问题，与“爬楼梯”问题模型类似，但目标是最小化路径成本。

1. 动态规划状态定义

我们定义一个数组 dp，其中 dp[i] 表示到达第 i 块地砖（1-based 索引）时所消耗的最小体力值总和。我们的目标是求出 dp[n]。

2. 状态转移方程

要想到达第 i 块地砖，只可能从以下两个位置过来：

  • 从第 i-1 块地砖走一步：此时的总消耗为 dp[i-1] + a[i]（到达第 i-1 块的最小消耗 + 踩上第 i 块的消耗）。
  • 从第 i-2 块地砖走两步：此时的总消耗为 dp[i-2] + a[i]（到达第 i-2 块的最小消耗 + 踩上第 i 块的消耗）。

为了使到达第 i 块地砖的消耗最小，我们应该选择这两条路径中成本更低的一条。因此，状态转移方程为：

3. 基本情况 (Base Cases)

  • dp[1]：到达第一块地砖的路径唯一（就是起点），所以 dp[1] = a_1。
  • dp[2]：到达第二块地砖的路径也唯一（从第一块走一步），所以 dp[2] = dp[1] + a_2 = a_1 + a_2。
  • 对于 ，我们就可以应用上面的状态转移方程。

4. 空间优化

观察状态转移方程可以发现，计算 dp[i] 只需要 dp[i-1] 和 dp[i-2] 的值。因此，我们没有必要保存整个 dp 数组，可以使用两个变量来滚动记录前两个状态的值，将空间复杂度从 优化到 。

  • 用 prev2 记录 dp[i-2] 的值。
  • 用 prev1 记录 dp[i-1] 的值。
  • 迭代计算 current = min(prev1, prev2) + a[i]，然后更新 prev2 和 prev1 继续下一轮计算。

代码

(注意：代码实现中使用 0-based 数组索引来对应 1-based 的地砖编号)

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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 prev2 = a[0];
    long long prev1 = a[0] + a[1];

    for (int i = 2; i < n; ++i) {
        long long current = min(prev1, prev2) + a[i];
        prev2 = prev1;
        prev1 = current;
    }

    cout << prev1 << 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 prev2 = a[0];
        long prev1 = a[0] + a[1];

        for (int i = 2; i < n; i++) {
            long current = Math.min(prev1, prev2) + a[i];
            prev2 = prev1;
            prev1 = current;
        }

        System.out.println(prev1);
    }
}

import sys

def solve():
    try:
        n = int(sys.stdin.readline())
        a = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    if n == 1:
        print(a[0])
        return

    prev2 = a[0]
    prev1 = a[0] + a[1]
    
    for i in range(2, n):
        current = min(prev1, prev2) + a[i]
        prev2 = prev1
        prev1 = current
        
    print(prev1)

solve()

算法及复杂度

  • 算法：动态规划

  • 时间复杂度：。

    • 我们只需要对地砖数组进行一次遍历。

  • 空间复杂度：。

    • 通过使用滚动变量，我们只需要常数级别的额外空间。