動的計画法（DP）は、競技プログラミングで避けて通れない重要テーマです。
しかし、初〜中級者の多くが共通してつまずくのが、
- 状態をどう定義するか
- 遷移式をどう作るか
という「考え方」の部分です。
特に AtCoder の典型問題である「足場ジャンプ（Frog 1）」は、
まさに“DP の基礎となる思考パターン”が詰まっています。
https://atcoder.jp/contests/dp/tasks/dp_a
この記事では、単に解法を示すのではなく、DP の本質を理解し、自分自身で状態遷移を組み立てられるようになることを目標に、丁寧に解説していきます。
導入：なぜ DP がわからなくなるのか？
多くの学習者が DP を苦手に感じる理由は、計算自体よりも「発想」が難しいからです。
- どの状態をメモすればいいの？
- 遷移式って何を根拠に作るの？
- 配列に何を入れればいいのかわからない…
こうした悩みは本当に多いですが、安心してください。
DP の本質は “小さな問題を積み上げる” ただそれだけ です。
まずは今回の問題を通して、
「状態定義 → 遷移式 → 実装」の一連の流れを一緒に辿っていきましょう。
問題の本質：やるべきことは「最小コストの積み上げ」
足場が N 個並んでいて、カエルは 1 から N へジャンプしていきます。
ジャンプできるのは以下の 2 パターン：
- i → i+1
- i → i+2
そしてジャンプには以下のコストがかかります：
|h[i] − h[j]|
つまり、
「どの足場を経由して N へ向かうと、総コストが最小になるか」
を求める問題です。
ここで重要なのは、
- 「未来のジャンプ先」を考える前に、
- まず“今いる足場までの最小コスト”がわかっていれば、次に進める
という構造があることです。これは DP が使える問題の典型構造です。
DP の考え方：状態を一つに固定すれば道が見える
DP を理解する第一歩は、状態を 1 つだけに固定することです。
今回なら次の 1 文に尽きます。
「足場 i にたどり着くために支払う最小コストを dp[i] とする」
これが 状態定義 です。
この一行が決まれば、解法の 8 割は終わったと言っても過言ではありません。
状態遷移の説明：過去から最小を拾ってくるだけ
足場 i へ到達する方法は、最大で 2 通りしかありません。
- 足場 i−1 からジャンプ
- 足場 i−2 からジャンプ
よって、以下のように「過去の最小値にコストを足すだけ」です。
■ 遷移式
dp[i] = min(
dp[i-1] + |h[i] - h[i-1]|,
dp[i-2] + |h[i] - h[i-2]|
)
サンプルの分解：実際に値を埋めてみる
入力例：
4
10 30 40 20
足場の高さは次の通り：
| 足場 | 高さ |
|---|---|
| 1 | 10 |
| 2 | 30 |
| 3 | 40 |
| 4 | 20 |
dp 配列の初期化
dp[1] = 0 （最初からいるのでコスト 0）dp 2
dp[2] = dp[1] + |10 - 30|
= 0 + 20
= 20dp 3
パターン1：1→2→3
dp[2] + |30 - 40| = 20 + 10 = 30
パターン2：1→3
dp[1] + |10 - 40| = 0 + 30 = 30
よって dp[3] = 30dp 4
パターン1：2→4
dp[2] + |30 - 20| = 20 + 10 = 30
パターン2：3→4
dp[3] + |40 - 20| = 30 + 20 = 50
よって dp[4] = 30実装例（Python / TypeScript）
Python
n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
dp[i] = min(
dp[i-1] + abs(h[i] - h[i-1]),
dp[i-2] + abs(h[i] - h[i-2])
)
print(dp[-1])
TypeScript（ケビン作成）
import * as fs from "fs";
function main(input: string): void {
const trimmedInput = input.trim();
const [rawN, rawHs] = trimmedInput.split(/\r?\n/);
const N = Number(rawN)
const Hs = rawHs.split(" ").map(Number);
const dp = Array(N).fill(0);
dp[1] = Math.abs(Hs[1] - Hs[0]);
for(let i=2; i<N; i++){
const beforeOne = Hs[i-1];
const beforeTwo = Hs[i-2];
const current = Hs[i];
let cost = 0;
const costA = dp[i-1] + Math.abs(beforeOne - current);
const costB = dp[i-2] + Math.abs(beforeTwo - current);
cost = Math.min(costA, costB)
dp[i] = cost;
}
console.log(dp[N-1]);
}
const inputData: string = fs.readFileSync("/dev/stdin", "utf8")
main(inputData);計算量：O(N) で高速に解ける
- 足場ごとに定数回の計算しか行わない → 計算量 O(N)
- メモリも dp と h の 2 配列で十分 → メモリ O(N)
まとめ：DP の本質は「状態」と「遷移」を考えるだけ
✔ 1. 状態定義が問題を決める
dp[i] = 足場 i にたどり着く最小コスト
✔ 2. 遷移式は「過去の最小値 + コスト」
ジャンプ可能な2パターンを比較するだけで遷移が作れます。
✔ 3. DP の本質は積み上げ
「未来を直接考えない」「今の状態の最小を確定して進む」これが動的計画法の考え方です。
最後に：Frog 1 を理解できれば、DP の世界が一気に開く
Frog 1 は DP の入門問題ですが、
「状態定義」→「遷移式」→「実装」 の流れをつかむには最適です。
この問題が理解できたら、類題として
- Frog 2（ジャンプ幅が K まで拡大）
- Frog 3（平方コスト）
- Typical DP まとめ問題
などにも自然と挑戦できるようになります。
DP が苦手でも、考え方がつかめれば必ず得意分野になります。
私もまだまだAtCoder勉強中ですが、
皆様が、これから DP を武器に競技プログラミングを楽しめるよう、
この記事が少しでも役に立てば嬉しいです！
