問題

這邊以 AtCoder Educational DP Contest 的類題來舉例，這題是 A - Frog 1，簡單來說一隻青蛙可以一次走兩步或是走一步，然後每一步的價值就是前一步或前兩步和這一步的高度差，然後要找從第一步到最後一步花費的最低價值

解法

簡單來說這很像是一題爬樓梯，只是爬樓梯通常會是要求幾種走法，而這一題要求的是最小價值，不過依然會是跟前面的狀態有相關，因此可以將 dp[0] 和 dp[1] 先定義，之後每一步都會是一階前或是兩階前再加上從那一階走到這一階的價值兩者的最小值，由此開始計算就可以得到答案了

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin >> n;
    vector<long long> stair(n);
    for(int i = 0;i < n;i++){
    	cin >> stair[i];
    }
    vector<long long> dp(n);
    dp[0] = 0;
    dp[1] = abs(stair[1] - stair[0]);
    for(int i = 2;i < n;i++){
    	dp[i] = min(dp[i - 1] + abs(stair[i] - stair[i - 1]),dp[i - 2] + abs(stair[i] - stair[i - 2]));
    }
    cout << dp[n - 1] << "\n";
    return 0;
}

時間複雜度

因為只要一層迴圈計算，所以是

總結

這一題是由最基本的 DP 題目下去延伸的，只要有寫過最基本的爬樓梯問題應該不難，思考也不會太過複雜，大家都可以嘗試看看