小红的地砖

思路

经典的动态规划入门题。小红站在第 1 块地砖上，想到达第 块地砖，每次可以往前走 1 步或 2 步，踩到每块砖都会消耗对应的体力值，求最小体力消耗。

是不是很眼熟？这就是「爬楼梯」问题的变体——加上了每一格的代价。

状态定义

设 表示从第 1 块砖走到第 块砖的最小体力消耗。

转移方程

第 块砖只可能从第 块或第 块走过来，所以：

$$

初始值

  • （起点不消耗体力）
  • （只能从第 1 块走一步到第 2 块）

举个例子

以样例 1 为例，：
0 0 - - 0
1 3 - - 3
2 2 3 0 0+2=2
3 1 2 3 2+1=3
4 0 3 2 2+0=2

答案为 ，对应路径 。

最终答案就是 。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    if(n==1){printf("0\n");return 0;}
    vector<long long> dp(n, 1e18);
    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();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        if (n == 1) {
            System.out.println(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(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(0);
        return;
    }
    const dp = new Array(n).fill(0);
    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]);
});

复杂度分析

  • 时间复杂度：，只需遍历一次数组。
  • 空间复杂度：，用于存储 dp 数组。可以优化到 ，因为每次转移只用到前两个状态。