小红的地砖

[题目链接](https://www.nowcoder.com/practice/734a67d1b09b486c8d7a676e4424e4f9)

思路

经典的动态规划入门题，类似「爬楼梯最小花费」。

状态定义

设 $dp[i]$ 表示从第 1 块地砖出发，走到第 $i$ 块地砖时消耗的最小体力值。

状态转移

小红每次可以向前走 1 步或 2 步，因此第 $i$ 块地砖只能从第 $i-1$ 块或第 $i-2$ 块走来：

$ $dp[i] = \min(dp[i-1],\; dp[i-2]) + a[i]$ $

初始化

$dp[0] = a[0]$ ：起点在第 1 块地砖，必须消耗 $a[0]$ 的体力。
$dp[1] = a[0] + a[1]$ ：只能从第 1 块走一步到第 2 块。

答案

$dp[n-1]$ 即为走到第 $n$ 块地砖的最小体力值。

样例演示

输入 [0, 3, 2, 1, 0]， $dp$ 数组为 [0, 3, 2, 1, 2]。路径 $1 \to 3 \to 5$ ，体力消耗 $0 + 2 + 0 = 2$ 。

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$ ，可优化为 $O(1)$ （只需保留前两个状态）

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<long long> a(n);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    if(n==1){
        printf("%lld\n",a[0]);
        return 0;
    }
    vector<long long> dp(n);
    dp[0]=a[0];
    dp[1]=a[0]+a[1];
    for(int i=2;i<n;i++){
        dp[i]=min(dp[i-1],dp[i-2])+a[i];
    }
    printf("%lld\n",dp[n-1]);
    return 0;
}

import java.util.Scanner;
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 = new long[n];
        dp[0] = a[0];
        dp[1] = a[0] + a[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + a[i];
        }
        System.out.println(dp[n - 1]);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(a[0])
else:
    dp = [0] * n
    dp[0] = a[0]
    dp[1] = a[0] + a[1]
    for i in range(2, n):
        dp[i] = min(dp[i-1], dp[i-2]) + a[i]
    print(dp[n-1])

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    if (n === 1) {
        console.log(a[0]);
        return;
    }
    const dp = new Array(n);
    dp[0] = a[0];
    dp[1] = a[0] + a[1];
    for (let i = 2; i < n; i++) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + a[i];
    }
    console.log(dp[n - 1]);
});