A93766 正经题解

题意分析
这是一道经典的线性动态规划问题，每次选择走一步或两步，求到终点的最小代价。
解题思路
我们先要知道，动态规划的根本——子问题该选择什么，即 $dp_i$ 应该表示什么。先来分析一个最简单的问题：

60 
||    30 35
|| 20 || ||

要跳到任何一块石阶上，青蛙只有两种跳法，从上上块石阶直接跳过来，或者从上一块石阶跳过来。因此我们可以发现，如果可以知道跳到上一块与上上块石阶的最小花费，就可以知道跳到这一块石阶的最小花费。那有没有什么可以确定的条件呢？青蛙不用动就已经在第一块石阶上，因此 $dp_1$ 为 $0$。青蛙只能从第一块石阶跳到第二块石阶上，因此 $dp_2$ 为第一、二块石阶的高度差。接下来，根据这些信息就可以得知第三块、第四块、第五块……
AC代码

#include <bits/stdc++.h>
using namespace std;
long long h[100005], dp[100005];

int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> h[i];
    }
    dp[0] = 1e9+7, dp[1] = 0;
    for(int i=2;i<=n;++i){
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout << dp[n];
    
    return 0;
}

滚动数组优化

#include <bits/stdc++.h>
using namespace std;
long long h[100005], dp[3];

int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> h[i];
    }
    dp[0] = 1e9+7, dp[1] = 0;
    for(int i=2;i<=n;++i){
        dp[2] = min(dp[1]+abs(h[i]-h[i-1]), dp[0]+abs(h[i]-h[i-2]));
        dp[0] = dp[1];
        dp[1] = dp[2];
    }
    cout << dp[2];
    
    return 0;
}

时间复杂度
$O(n)$，看到上一篇题解，我也要吐槽下了，橙题都要用 $AI$ 还不抓紧了学，直接复制连思路都不了解下那还打什么竞赛。