题解 | 小红的地砖

/*
从第1块地砖走到第i + 1块地砖所需消耗的最小体力值记为dp[i],dp[0] = a[0],dp[1] = a[0] + a[1],i >= 2时，dp[i] = min{dp[i - 1],dp[i - 2]} + a[i]，如此可得dp[n - 1];
但是可以优化一下，只用两个变量pre和cur滚动记录dp[i - 1]和dp[i - 2]的值，这样可以降低空间复杂度
*/

#include <stdio.h>
#include <stdlib.h>

int main() {
    //读取数据
    int n;
    scanf("%d\n", &n);
    int *a = (int *)malloc(sizeof(int) * n);
    if(a == NULL){
        printf("Failed Malloc!\n");
        return -1;
    }
    for(int i = 0; i < n; i++){
        scanf("%d", a + i);
    }
    
    //分情况，如果n为1或2，直接打印结果
    if(n == 1){
       printf("%d\n", a[0]);
    }
    else if(n == 2){
        printf("%d\n", a[0] + a[1]);
    }
    else{//其余情况，用pre和cur滚动记录dp[i - 1]和dp[i - 2]的值,最终cur存储dp[n - 1]的值
        int pre = a[0];
        int cur = a[0] + a[1];
        for(int i = 2; i < n; i++){
           int next = (pre < cur ? pre : cur) + a[i];
           pre = cur;
           cur = next;
        }
        printf("%d\n", cur);
    }
    
    //释放空间
    free(a);

    return 0;
}