题解 | 小红的地砖

#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int a[n+3];
    int dp[n+3];
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        dp[i]=0;
    }
    /*思路：
    这个类型的动态规划我们没有见过，相对于背包问题的话，这是不能套模型的，因为两个问题有明显的区别！！！
    这个时候，我先联想到了走楼梯的问题！！！同点：都是走两种方法！但有了判断条件————要最小体力值
    我们先试着写下解法图：
         /->dp[n-1]
        /
    dp[n]            
        \
         \->dp[n-2]
我们可以算出每个格子的最少力！！在去推最后的格子！！
dp[n-1]的最少力，不就来自dp[n-2],dp[n-3]，同时要知道这里的dp[k]都是最小的了
总结：我们由最前面开始推，把每个格子的最少力算出，去推后面的！这就复合了动态规划的核心：大问题变为了多个小问题！！
    */
dp[1]=0;
dp[2]=a[2];
for(int i=3;i<=n;i++){
    int yibu=dp[i-1];
    int rebu=dp[i-2];
    dp[i]=(yibu>rebu?rebu:yibu)+a[i];
}
printf("%d",dp[n]);


}