DPまとめコンテスト解説（開発中）

はじめに

こんにちは、競プロ歴1年（多分）のmikan0131（AtCoder茶）です
僕のQiitaの初投稿はDPまとめコンテストの解説です

初心者の解説なので、わかりにくいかもしれないですが、ぜひ見ていってください！

A Frog1

問題

Nこの足場があります。足場には1, 2, ...., Nと番号が振られています。各i(1 <= i <= N)いついて、足場iの高さはh_iです。
最初、足場1にカエルがいます。カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。
・足場iにいるとき、足場i + 1またはi + 2へジャンプする。このとき、ジャンプ先の足場をjとすると、コスト|h_i - h_j|を支払う。
カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

• 入力はすべて整数である
• 2 <= N <= 10^5
• 1 <= K <= 100
• 1 <= h_i <= 10^4

入力

N K
h_1 h_2 ... h_N

出力

カエルが支払うコストの総和の最小値を出力せよ。

解説

動的計画法の基本といえる問題です。
足場iにおいて、足場i - 2からジャンプするか、足場i - 1からジャンプするかで、コストの総和が小さいほうを採用するのを、足場3からNまで繰り返します。足場1のコストは0、足場2のコストは、足場1からジャンプするしかないため、一意に定まります。

解答

solve.cpp

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

int N, h[100009], A[100009], B[100009];
int dp[100009];

int main() {
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> h[i];
  for (int i = 2; i <= N; i++) {
    A[i] = abs(h[i] - h[i - 1]);
  }
  for (int i = 3; i <= N; i++) {
    B[i] = abs(h[i] - h[i - 2]);
  }
  dp[1] = 0;
  dp[2] = A[2];
  for (int i = 3; i <= N; i++) {
    dp[i] = min(dp[i - 1] + A[i], dp[i - 2] + B[i]);
  }
  cout << dp[N] << endl;
  return 0;
}