AtCoder Educational DP Contest A - Frog 1

はじめに

AtCoder初心者が勉強していく記事です。
初学者の時にわからなかったことって、慣れてくると忘れてしまうかとおもいます。
後の初学者の方のためにもくどいくらいにコメントを書いていきます。

問題を解く

動的計画法(DP: Dynamic Programming)関連の問題が沢山集まったEducational DP Contestの問題を解いていきます。
今回はこちら。
A - Frog 1

//A - Frog 1
#include <iostream>
using namespace std;

int main(){
  int n;
  //int nを入力
  cin >> n;

  //足場iにおける高さを入力
  int h[n];
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  //足場iにおけるコストの最小値
  int dp[n];
  //スタート時点ではジャンプしていないのでコストゼロ
  dp[0] = 0;
  //足場1に行く方法は足場0から+1でジャンプする1通りのみ
  dp[1] = abs(h[1] - h[0]);

  /*足場2以降に関して計算。
  足場iに到達する方法は
  ①足場i-2から+2のジャンプ or ②足場i-1から+1のジャンプ
  */

  for(int i = 2; i < n; i++){
    //①の場合に関して計算しdp[i]に代入
    dp[i] = dp[i - 1] + abs(h[i] - h[i-1]);
    //さらに②の場合も計算。①と②を比較した際の最小値(min)が足場iに到達するための最小コスト
    dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i-2]));
  }

  //最後の足場におけるコストを出力。
  cout << dp[n-1] << endl;
  return 0;
}