题解 | 小红的地砖

/*
从第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];
*/

#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);
    }
    
    //构造数组dp，维护子问题的解
    int *dp = (int *)malloc(sizeof(int) * n);
    if(dp == NULL){
        printf("Failed Malloc!\n");
        return -1;
    }
    for(int i = 0; i < n; i++){
        if(i == 0){
            dp[i] = a[0];
        }
        else if(i == 1){
            dp[i] = a[0] + a[1];
        }
        else{
            int tmp = dp[i - 1] < dp[i -2] ? dp[i - 1] : dp[i - 2];
            dp[i] = tmp + a[i];
        }
    }

    //dp[n - 1]即为所求结果，打印即可
    printf("%d\n", dp[n - 1]);

    //释放空间
    free(a);
    free(dp);
    return 0;
}