题目链接

小红的地砖

题目描述

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

输入:

  • 第一行输入一个整数 ，表示地砖的数量
  • 第二行输入 个整数 ，表示走到第 块地砖需要消耗的体力值

输出:

  • 输出一个整数，表示小红走到第 块地砖时消耗的最小体力值

解题思路

这是一个动态规划问题，可以通过以下步骤解决：

  1. 关键发现：

    • 每次可以走一步或两步
    • 到达每个位置的最小体力值只与前两个位置有关
    • 需要累加经过的地砖的体力值

  2. 解题策略：

    • 使用dp数组记录到达每个位置的最小体力值
    • 对每个位置，考虑从前一个位置走一步或从前两个位置走两步
    • 选择较小的体力值

  3. 具体步骤：

    • 初始化dp数组，dp[i]表示到达第i个位置的最小体力值
    • 状态转移：dp[i] = min(dp[i-1], dp[i-2]) + a[i]
    • 最后返回dp[n-1]

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> dp(n, INT_MAX);
    dp[0] = a[0];
    if(n > 1) dp[1] = a[1];
    
    for(int i = 2; i < n; i++) {
        dp[i] = min(dp[i-1], dp[i-2]) + a[i];
    }
    
    cout << dp[n-1] << endl;
    return 0;
}

import java.util.*;

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();
        }
        
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = a[0];
        if(n > 1) dp[1] = 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]);
    }
}

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

dp = [float('inf')] * n
dp[0] = a[0]
if n > 1:
    dp[1] = a[1]

for i in range(2, n):
    dp[i] = min(dp[i-1], dp[i-2]) + a[i]

print(dp[n-1])

算法及复杂度

  • 算法：动态规划
  • 时间复杂度： - 需要遍历一次数组
  • 空间复杂度： - 需要dp数组存储状态

注意：

  1. 需要特别处理n=1和n=2的情况
  2. 初始化dp数组时要用最大值
  3. 状态转移时需要考虑前两个位置
  4. 最终结果是dp[n-1]而不是dp[n]