Educational DP Contest A - Frog 1

問題概要

問題のリンク

要素$N$個の配列$h$がある。
点$1$からスタートして$N$にたどり着くまで移動する。ある点$i$からは$i+1$または$i+2$に移動することができる。

移動先の点を$j$とすると、$|h_j - h_i|$が移動コストとなる。移動コストの最小値を求めよ。

制約条件

• 入力はすべて整数である。
• $2≤N≤10^5$
• $1≤h_i≤10^4$

考えたこと

まんまこれでびっくりした。 → C - 柱柱柱柱柱
前やったときのを思い出しながら解いた。

点$i$における最適値(=最小値)は1個前か2個前の値に依存する。仮に点$i$において1個前の値が最適値になるのであれば、その$i-1$の値は1個前と２個前のどちらかに依存しているかが問題となってくる。
これを逐次保存して管理していくことにより計算量を抑える。

遷移式は以下のようになる。
初項と第一項は自明で第二項以降は1個前か2個前どちらの値に最適値が依存しているかを判定していく。

vector<int> dp(n);
dp[0] = 0;
dp[1] = abs(h[1]-h[0]);
for(int i = 2; i < n; i ++) {
    dp[i] = min(abs(h[i]-h[i-1]) + dp[i-1], abs(h[i]-h[i-2]) + dp[i-2]);
}

計算量は $O(N)$です。

解答

C#の解答

using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int[] h = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(dp(n,h)[n-1]);
    }
    static int[] dp(int n, int[] h) {
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = Math.Abs(h[1]-h[0]);
        for(int i = 2; i < n; i ++) {
            dp[i] = Math.Min(Math.Abs(h[i]-h[i-1])+dp[i-1], Math.Abs(h[i]-h[i-2])+dp[i-2]);
        }
        return dp;
    }
}

C++の解答

#include <bits/stdc++.h>
using namespace std;

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